## Back to School '16: Times Table

View as PDFhas bought a number of times table sets in preparation for the difficult math in the upcoming school year. A times table set is a rectangular collection of columns, with respective heights of a times table which somehow helps to visualize the math.

Consider a 4 by 4 times table.

× | 1 | 2 | 3 | 4 |
---|---|---|---|---|

1 | 1 | 2 | 3 | 4 |

2 | 2 | 4 | 6 | 8 |

3 | 3 | 6 | 9 | 12 |

4 | 4 | 8 | 12 | 16 |

These products are the heights of a set shown below.

```
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16
```

He wants to stack them on top of each other times within an originally empty by grid to form a cool 3D structure. When stacked, gravity takes effect on the individual columns causing them to drop down. The grid has a top-left corner at and a bottom right corner at . He may put more than one set at the same time. This effectively multiplies all the numbers (heights) in the times table.

```
2 4 6 8
4 8 12 16
6 12 18 24
8 16 24 32
```

After stacking these sets together, wants to take a finger walk in the grid starting at position . He wants to take the longest finger walk on a strictly increasing path. Output the largest sum of a such a path. He may only finger walk to adjacent blocks (up, down, left, right).

#### Input Specification

The first line contains two space separated integers, , the number of columns and rows on the grid and the number of times that will place multiplication table sets.

The next lines will contain 5 integers, `x y w h n`

where is the top left corner of the multiplication table set(s). is the width and is the height of the set(s). is the number of sets to be inserted. It is guaranteed that the whole rectangle is within the grid.

Finally, the last line of input will contain `c r`

, is the starting position of the finger walk. It is guaranteed that the coordinates are within the grid.

#### Constraints

##### Subtask 1 [20%]

##### Subtask 2 [80%]

#### Output Specification

A single integer, the largest sum of the longest finger walk possible modulo .

#### Sample Input 1

```
5 4 3
1 1 3 3 1
3 3 3 2 2
2 4 2 1 4
2 1
```

#### Sample Output 1

`35`

#### Explanation for Sample Output 1

The structure is:

```
1 2 3 0 0
2 4 6 0 0
3 6 11 4 6
0 4 12 8 12
```

The longest path is: .

#### Sample Input 2

```
5 5 1
1 1 5 5 1
2 2
```

#### Sample Output 2

`92`

## Comments