Item Acquired

You are building a game that obtains items by driving a car in a 2D map.

There are $N$ boxes on the map from which items can be obtained. The position of the $i$-th box is located at $(x_i, y_i)$, and every time the car passes through this location, it can obtain $w_i$ items.

The car moves in a direction parallel to either the x-axis or the y-axis. Each movement of the car can be presented as $d$ and $v$. If $d=0$, the car moves $v$ units in the direction of increasing x-coordinate; if $d=1$, the car moves $v$ units in the direction of increasing y-coordinate; if $d=2$, the car moves $v$ units in the direction of decreasing x-coordinate; if $d=3$, the car moves $v$ units in the direction of decreasing y-coordinate.

In this case, the items from a box located at the starting position of the movement cannot be obtained. In other words, when moving from $(s_x, s_y)$ to $(e_x, e_y)$, the items from the box at $(s_x, s_y)$ cannot be obtained, while the item at $(e_x, e_y)$ can be obtained.

The car starts at $(1, 1)$ and makes a total of $Q$ movements. Given the direction and distance of each movement, determine the total number of items obtained during the $Q$ movements.

• $1 \le N \le 200\,000$
• $1 \le Q \le 200\,000$
• $1 \le x_i \le 200\,000$
• $1 \le y_i \le 200\,000$
• $1 \le w_i \le 200\,000$
• $0 \le d_j \le 3$
• $1 \le v_j \le 200\,000$
• The positions of the boxes are different from each other.
• At every moment, the car's x and y coordinates are between $1$ and $200\,000$, inclusive.
• All given numbers are integers.

1. (9 points) $N \le 2\,000$, $Q \le 2\,000$, $x_i \le 1\,000$, $y_i \le 1\,000$, $w_i \le 10$, and at every moment, the car's x and y coordinates are at most $1\,000$.
2. (17 points) $N \le 2\,000$, $Q \le 2\,000$, $w_i \le 10$.
3. (15 points) All boxes have distinct x-coordinates and distinct y-coordinates.
4. (37 points) $w_i = 1$.
5. (22 points) No additional constraints.

The first line contains the number of boxes $N$ and the number of moves $Q$, separated by a space.

The next $N$ lines follow. The $i$-th line contains three integers $x_i, y_i, w_i$, separated by spaces. This means that the $i$-th box is located at $(x_i, y_i)$, and each time the car passes through this position, it obtains $w_i$ items.

The next $Q$ lines follow. The $j$-th line contains two integers $d_j, v_j$, separated by a space. This means that the car moves $v_j$ units in direction $d_j$.

Print the total number of items obtained during the $Q$ moves.