shit

Scrooge McDuck
Description
Scrooge McDuck likes his treasure very much. That is why he likes to play a funny game.

He builds a labyrinth of coins and tries to escape from it. You can think of the labyrinth as a rectangular field. Each cell of the field contains 0 or more coins.

When Scrooge McDuck steps on a cell, he can take only a single coin from this cell, and only if there are any coins. Scrooge McDuck can escape the field, only if he is surrounded by empty cells.

Scrooge McDuck always wants to go to the neighbouring cell with most coins. BUT if there are more than one cells with the same amount of coins (the largest), he chooses a cell (always the largest) from the order left, right, up, down

If Scrooge McDuck cannot go in any direction, he is out of the labyrinth

Examples

Scrooge McDuck is worried, not about his life, but if the coins he collect will be enough. Your task is to tell him how many coins he will collect, following the rules above.

Input
Read from the standard input
On the first line find N and M
The size of the labyrinth
On the next N lines find M integer values, separated by a space
The input data will always be valid and there is no need to check it explicitly
The starting location of Scrooge McDuck will be marked as the only 0
Output
Print to the standard output
On the single line, print the number of coins Scrooge McDuck can collect, following the rules
Contraints
2 <= N <= 10
2 <= M <= 10
Each cell can contain up to 1024 coins
Sample tests
Input
4 3
3 2 4
2 0 3
1 1 5
2 2 5
Output
22
Input
3 3
10 10 0
10 10 10
10 10 10
Output
78
Input
3 3
10 10 10
10 0 10
10 10 10
Output
80
Input
2 3
0 5 2
2 5 3
Output
15

///////////////////////////////////////////////////////////////////

Matrix Max Sum
Description
Write a program that finds the maximum sum between two given coordinates in a matrix. The coordinates are provided as a list of pairs, such as 2 3 -4 -2 where 2 3 is the first pair and -4 -2 is the next one. The first number of the pair is the row coordinate R and the second one is the column coordinate C.

You need to follow a path from R to C and sum up all the values you encounter in cells. For example, with coordinates 2 3 you start from the beginning of the 2nd row and move towards the 3rd column. When you reach the column, you go up because the column coordinate 3 is positive.

With coordinates -4 -2 you start from the end of the 4th row (because -4 is negative) and move towards the 2nd column. When you reach it, you go down (-2 is negative).

Check the following picture for a clearer idea.

table

The path 2 3 yields a sum of 17 which is higher than the sum you obtain by following -4 -2 (15)

Print the maximum sum you find to the standard output.

Note
You always have to move horizontally in rows and vertically in columns. For example, in the above picture, the correct path with coordinates -4 -2 is 3 -> 2 -> 5 -> 3 -> 2 and NOT 3 -> 4 -> 3 -> 6 -> 2.

Input
On the first line, you receive an integer N - the number of rows in the matrix
On the next N lines, each row of the matrix is given, with columns separated by a space
On the last line, the R and C coordinates are given, separated by spaces
Output
On the only line of output, print the maximum sum found.
Constraints
N will be an integer between 5 and 20, inclusive.
All rows have the exact same length, also between 5 and 20, inclusive.
The R and C coordinates will always be valid and inside the matrix.
The R C pairs will be at least 1 and no more than 20.
Matrix elements will have values in range -5000 and 5000.
Sample Tests
Input
6
1 2 3 4 5 6
2 3 4 5 6 7
6 5 4 3 2 1
3 4 5 6 7 8
4 5 6 7 8 9
9 8 7 6 5 4
3 5 3 -5 -4 -2
Output
43
Input
5
1 22 3 41 5 2
2 13 4 -5 6 5
-6 5 9 31 2 8
3 14 5 -6 7 4
4 -5 6 -7 8 7
-3 -3 3 3 4 -3 -4 3
Output
61

////////////////////////////////////////////////////////////////////

Jump Around
Description
Pesho is a funny cangaroo. He wants to jump around all day and night. Yet his mom is not so happy about that, she doesn't let him out. Of course Pesho tried many times to escape, but his mother used to be the National Cangaroo jump champion, so she can jump faster and higher than him. Still she is not that smart, so Pesho decided that he can trick her by jumping using a sequence of jumps.

Your task is to calculate if Pesho can escape from his mother, using the given sequence of jumps.

You are given a field of size N x M where the values are as follows: On the first row the numbers are from 1 to M, on the second row – from M+1 to 2*M, on the third – from 2*M +1 to 3*M, etc…

By given position in the field, and using the patterns given, calculate if Pesho can escape from his mother.

Examples

You are also given a sequence of jumps over the field. The jumps are described with change to the row and column, i.e. when on position (R, C) with jump (-2, 3), Pesho will go to position (R-2, C+3).
When the sequence of jumps is over, Pesho must start the same sequence again.

If Pesho goes outside the field, he has escaped, if Pesho goes to a previously visited position, he is caught.

Input
Read from the standard input

On the first line, find the numbers N, M and J. (J is number of jumps)
On the second line, find the start position, R and C
On the next J lines, find the jumps
Output
Print on the standard output

On the single line, print
"escaped SUM_OF_NUMBERS", if Pesho escapes his mother
"caught NUMBER_OF_JUMPS", if Pesho is caught
Constraints
N and M will always be between 1 and 500
J will be between 1 and 1000
Sample tests
Input
6 7 3
0 0
2 2
-2 2
3 -1
Output
escaped 89