20549번 - 인덕이의 고민

오리를 좋아하는 인덕이는 오리를 바라보며 마음의 안식을 얻는다. 오리는 N×N의 정사각형 모양으로 이루어진 인경호에서 유유자적하게 헤엄을 친다. 인경호는 1×1 크기의 칸으로 나누어져 있다.

각각의 칸은 (X, Y)로 나타내며, X는 가장 위에서부터 떨어진 칸의 개수, Y는 가장 왼쪽으로부터 떨어진 칸의 개수이다. X와 Y는 0부터 시작한다. 

그런 인덕이에게 요즘 큰 고민이 생겼다. 기껏 먹이를 주어도 먹이가 떠내려가서 오리가 다 먹지 못하기 때문이다.

고민하던 인덕이는 1학년 때 배웠던 생명과학 과목의 내용을 활용하면 오리의 유전자에 변형을 가하여 원하는 대로 이동시킬 수 있다는 것을 알게 되었다.

단, 너무 오래전에 들은 과목이기 때문에, 이 방법은 아래와 같은 제한사항이 붙는다.

• 체스에서 각각 나이트, 비숍, 룩이 이동하는 방향으로만 이동시킬 수 있고, 도착 지점에 먹이가 있으면 그 지점에 있는 먹이를 먹는다. 오리는 인경호 바깥으로 이동할 수 없다.
• 한 번의 변형에서 이동 명령에 따라 오리의 유전자는 과부하를 받고, 한번 이동하고 나면 변형이 풀린다.

오리가 과부하를 많이 받으면 인덕이도 슬퍼한다.

오리가 모든 먹이를 먹으면서 가장 과부하를 적게 받게 만들어서 인덕이의 고민을 덜어주자!

첫째 줄에 인경호의 가로, 세로 크기 N(3 ≤ N ≤ 50)이 주어진다.

두 번째 줄에 오리를 각각 나이트,  비숍, 룩이 갈 수 있는 이동으로 이동시킬 때, 오리가 받는 과부하의 양 A, B, C (1 ≤ A, B, C  ≤ 50)이 차례대로 주어진다.

세 번째 줄에는 오리의 시작 위치의 x좌표, y좌표에 해당하는 X,Y(0 ≤ X, Y ≤ N-1)가 주어진다.

그 다음줄에 먹이의 수 M(1 ≤ M ≤ 4)이 주어진다

M줄에 걸쳐서 먹이의 x좌표, y좌표에 해당하는 X_i, Y_i (0 ≤ X_i, Y_i ≤ N -1) 가 차례대로 주어진다.

오리의 시작위치와 각 먹이의 좌표는 전부 서로 다르게 주어진다.

유전자 변형을 이용해서 오리가 주어진 먹이를 모두 먹게 되었을 때 오리가 받는 과부하의 총합의 최소를 출력하자.

나이트, 비숍, 룩이 한번의 이동으로 도달할 수 있는 칸은 각각 다음과 같다.

그림 출처 : 위키백과(https://ko.wikipedia.org/wiki/%EB%A3%A9_(%EC%B2%B4%EC%8A%A4)

위 예시는 N이 8일때의 예시이며, N의 크기가 증가하거나 감소함에따라 룩이나 비숍이 도달 할 수 있는 칸도 증가하거나 감소한다.