연습문제

함께하는 효도

난이도
Lv. 3
제출
896 명
참가자
365 명
정답률
43.97 %
지원 언어
C
C++
Java
Python
JavaScript
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
JavaScript 2초 1024MB
Python 2초 1024MB
C++ 1초 1024MB
Java 2초 1024MB
C 1초 1024MB

남우는 m명의 친구를 불러 나무에서 열매를 수확하는 일을 맡겼습니다. 나무들은 n * n 크기의 격자 모양의 땅 위의 모든 칸에 심어져 있고, 각 나무마다 가능한 열매 수확량이 주어져 있습니다.



친구들은 n * n 크기의 격자 내의 서로 다른 위치에서 출발하여 1초에 1칸씩 상하좌우 인접한 칸 중 한 곳으로 움직일 수 있으며, 최종적으로 모든 열매 수확량의 합을 최대로 만들고자 합니다. 이때 각 칸에서 열매를 수확하는데 걸리는 시간은 0초이며, 한 나무에 여러 친구가 방문하게 되더라도 열매는 딱 한 번만 수확이 가능합니다. 또, 친구들끼리 이동하는 도중 만나게 되는 것 역시 가능합니다.


m명의 친구들이 3초 동안 최대로 얻을 수 있는 열매 수확량의 총 합을 구하는 프로그램을 작성해보세요.



본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.

제약조건

[조건 1] 2 ≤ n ≤ 20

[조건 2] 1 ≤ m ≤ 3

[조건 3] 1 ≤ 가능한 열매 수확량 ≤ 1,000

입력형식

첫 번째 줄에 n과 m이 공백을 사이에 두고 주어집니다.


두 번째 줄부터는 n개의 줄에 걸쳐 각 행에 해당하는 n개의 가능한 열매 수확량 정보가 공백을 사이에 두고 주어집니다.


n + 2번째 줄부터는 m개의 줄에 걸쳐 각 친구의 위치 정보 ( Xi , Yi )가 공백을 사이에 두고 주어집니다. 이는 친구가 ( Xi 행, Yi 열)에 위치해 있음을 뜻하며, 처음 위치가 겹쳐져 주어지는 경우는 없다고 가정해도 좋습니다.

출력형식

첫 번째 줄에 얻을 수 있는 최대 열매 수확량의 합을 출력하세요. 단, 처음 시작하는 칸의 경우 0초 때 열매 수확이 가능함에 유의합니다.

입력예제1

4 2
20 26 185 80
100 20 25 80
20 20 88 99
15 32 44 50
1 2
2 3
출력예제1

633

다음과 같이 움직이면 3초 안에 열매 수확량 총합 633을 얻을 수 있습니다.


목록