E. Fortress Fall
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Please refer to the statements in the attachment files

Input

Please refer to the statements in the attachment files

Output

Please refer to the statements in the attachment files

Example
Input
6
4 1 2
4 5 6 7
5 2 8
0 -1 -2 -6 7
6 -1 -2
1 2 3 4 5 6
6 3 4
-1 0 0 1 2 3
6 -3 -4
1 0 0 -1 -2 -3
5 1 -10
-9 2 -5 3 -7
Output
35
56
0
23
23
165
Note

Please refer to the statements in the attachment files