Back to School '16: Times Table

View as PDF

Submit solution


Points:15 (partial)
Time limit:1.0s
Memory limit:256M
Author:

Problem types

atarw has 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 atarw to visualize the math.

times table set

Consider a 4 by 4 times table.

times table

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 M times within an originally empty C by R 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 (1, 1) and a bottom right corner at (C, R). 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, atarw wants to take a finger walk in the grid starting at position (c, r). 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, C R M, the number of columns and rows on the grid and the number of times that atarw will place multiplication table sets.

The next M lines will contain 5 integers, x y w h n where (x, y) is the top left corner of the multiplication table set(s). w is the width and h is the height of the set(s). n 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, (c, r) is the starting position of the finger walk. It is guaranteed that the coordinates are within the grid.

Constraints

Subtask 1 [20%]

1 \le C, R, M \le 100
1 \le n \le 10

Subtask 2 [80%]

1 \le C, R \le 500
1 \le M \le 100,000
1 \le n \le 100

Output Specification

A single integer, the largest sum of the longest finger walk possible modulo 1\,000\,000\,007.

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: 2 \rightarrow 4 \rightarrow 6 \rightarrow 11 \rightarrow 12.

Sample Input 2

5 5 1
1 1 5 5 1
2 2

Sample Output 2

92

Comments

There are no comments at the moment.