PLAYGROUND

Submit solution
Points: 100
Time limit: 1.0s
Memory limit: 493M
Problem type

Bản đồ khu vui chơi là một hình chữ nhật kích thước M×N ô vuông. Khu vui chơi có một cổng vào đặt tại ô (1,1) và một cổng ra đặt tại ô M×N. Mỗi ô (i,j) được bố trí một trò chơi, giá vé vào ô (i,j) là C[i,j]. Tại mỗi ô khách có thể di chuyển sang các ô chung cạnh bên phải hoặc phía dưới.

Vào một ngày nghỉ, Bin quyết định tham quan khu vui chơi. Trong khu vui chơi có một trò chơi Bin rất thích đặt tại ô (u, v) và nhất định Bin phải tham gia trò chơi này. Sau khi chơi các trò chơi xong Bin phải ra ở cổng ra tại ô M×N.

Yêu cầu: Giúp Bin tìm cách di chuyển để chơi trò chơi mình thích và tốn ít tiền nhất.

Input:

  • Dòng 1: chứa 4 số M, N, u, v ( 3 ≤ M, N ≤ 1000; 1 ≤ u ≤ M; 1 ≤ v ≤ N);

  • M dòng tiếp theo, mỗi dòng chứa N số, với C[i,j] là chi phí ô (i,j). (0 ≤ C[i,j] ≤ 10000)

Output:

Ghi chi phí ít nhất tìm được

Sample Input

4 5 2 3
5 6 4 4 1
1 2 9 1 5
1 1 1 2 3
4 6 5 1 4

Sample Output

25

Comments