Snack Attack is a four player minigame in Super Mario Party and you can view how the game is actually played here.

The goal of the game is to catch as many kernels of popcorn that fall from the sky using the cups on top of each players' head. In addition to popcorn, boulders will fall from the sky. The boulders are too big to catch with the cup, and so if hit by one, the player will lose half of their current popcorn kernels in the cup.

The original game is set in a circular area, but in this problem we will assume it is a square grid for simplicity. If a popcorn kernel falls onto some cell $(r,c)$ at time $t$ and a player is also at the same cell at the same time, this player will get a popcorn kernel. On the other hand, if at time $t$, a boulder falls onto cell $(r,c)$, this player will lose $\lceil h/2\rceil$ popcorn kernels, where $h$ is the current number of popcorn kernels in their cup (e.g., if you now only have 3 popcorn kernels, you will lose 2 and only 1 is left). The players can move at a speed of 1 cell per second and we assume that movement is not affected by any popcorn or boulders. In other words, each second a player can move from the current position to any adjacent cell (on the left, right, top or bottom) or stay at the same location, and they are not slowed down by all of the popcorn nor will they be stunned by a boulder hit.

Given the positions of all falling popcorns and boulders, the time that each will fall, and the initial position of the player, we want to know what is the maximum amount of popcorn this player can catch if they play through until the end.

Input Specification

The first line of the input contains three integers, $n$ ($0<n\le 100$), $p$ ($0\le p\le 1000$), and $b$ ($0\le b\le 1000$). This means the area will be described as an $n\times n$ matrix and there will be $p$ popcorn kernels and $b$ boulders that will rain upon the players throughout the game. Each cell is labeled by the pair $(r,c)$, ($0\le r,c<n$) where $r$ is the row and $c$ is the column of the cell (note that the rows and columns of the matrix are 0-indexed).

The next line contains two integers $s_r$ and $s_c$ ($0\le s_r,s_c<n$), which is the coordinate of the cell that the player starts (i.e. time $0$).

The next $p$ lines each contain three integers $r_i,c_i,t_i$, which means that at time $t_i$ ($1\le t_i\le 100$), there is one popcorn kernel falling down onto cell $(r_i,c_i)$.

The next $b$ lines each contain three integers $r_j,c_j,t_j$, which means that at time $t_j$ ($1\le t_j\le 100$), there is one boulder falling down at grid $(r_j,c_j)$.

There won't be any boulders or popcorns at time 0.

At the same time, there won't be both popcorn and boulders falling into the same position. There also won't be two boulders falling into the same position at the same time.

There CAN be multiple popcorn kernels falling into the same position at the same time.

Output Specification

The output only contains 1 integer, which is the maximum number of popcorn kernels the player can get.

Sample Input

5 4 2
2 2
2 3 1
1 4 3
1 2 1
1 0 3
2 4 2
1 3 2

Sample Output

2

Explanation for Sample Output

For the sample test case, one of the best solutions is shown as follows:

$(2,2)$ (time 0) → $(1,2)$ (time 1, get 1 popcorn kernel) → $(1,1)$ (time 2) → $(1,0)$ (time 3, get 1 popcorn kernel).

Source of pictures and descriptions: https://www.mariowiki.com/Snack_Attack. You can also find more details about the game from this site.

Scoring

For 50% of the test data, $n\le 20$.

For 100% of the test data, $n\le 100$, $p,b\le 1000$, all time $t\le 100$.

For 15% of the test data, $b=0$ (no boulders).

There are 20 test cases, 5 points each.