## coffee run

View as PDF

Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem types

deren and auo missed each other a lot. when they finally get together, deren wants to make auo happy by bringing coffee beans, because auo loves coffee!

the big day comes. deren and auo are going to meet. they are on an $$r$$ x $$c$$ matrix .deren starts from the cell $$1$$ x $$1$$ and moves towards auo. on his way, deren wants to collect coffee beans. there are $$m[r_i][c_i]$$ coffe beans at the $$r_i$$th row and $$c_i$$th column. deren starts at the position (1, 1) and can only move downwards or rightwards. given auo's location on the matrix, can you find the maximum amount of coffee beans deren can collect before meeting auo. when deren moves to a cell, he collects all the coffee beans in that cell (including the one auo is located at).

#### constraints:

$$r_a, c_a <= r, c, m[r_i][c_1] <= 1000$$

#### input:

the first line will contain the numbers $$r$$, $$c$$ (dimensions of the matrix) and $$r_a$$, $$c_a$$ (auo's location).

following $$r$$ lines will contain $$c$$ numbers each. denoting the amount of coffee beans at the cell ($$r_i$$, $$c_i$$), namely $$m[r_i][c_i]$$.

#### output:

you should print a single number, the maximum amount of coffee beans deren can collect before meeting auo.

#### examples

input 1:

3 5 3 4
1 3 2 4 6
2 3 5 7 1
1 9 8 3 1

output 1:

27

input 2:

3 3 3 3
3 4 5
5 1 5
7 2 4

output 2:

21
##### explanation:

on the first example, deren starts on (1,1) and goes to (3,4). suppose the path is $$(1,1) - (1,2) - (2,2) - (3,2) - (3,3) - (3,4)$$. along this path, deren collects 1, 3, 3, 9, 8, and 3 coffee beans respectively and 27 coffee beans in total. this is the maximum, so our answer is 27.