출발지에서 도착지 까지 가는 최단 비용을 구하는 문제이다. 단, 갈수 있는 방향은 상,하,좌,우 이다. 격자안의 숫자는 그 격자를 통과하는데 드는 비용이다.

입력형식

• 첫 줄에는 행,렬의 수가 들어오고 (행, 열의 크기는 200 이하)이고
• 다음 줄 부터는 (행,렬)의 비용이 들어온다. 다음 줄 에는 출발지와 도착지가 행,렬의 순서로 입력된다.
  격자안의 숫자는 모두 자연수이다.

출력형식

주어지는 모든 수와 결과값은 int 범위를 만족합니다.

입출력 예

입력

4 4
1 10 2 1
2 10 3 2
3 2 6 3
1 1 10 2
1 1
3 4

출력

17

채점데이터:Fate