Item Collection

You are building a game where a car moves on a two-dimensional map and collects items.

The map has $N$ boxes from which items can be collected. The position of the $i$-th box is $(x_i, y_i)$, and each time the car passes this position, it gets $w_i$ items.

The car moves in a direction parallel to the $x$-axis or the $y$-axis. A move is given by two integers $d$ and $v$. If $d = 0$, the car moves $v$ in the direction of increasing $x$. If $d = 1$, it moves $v$ in the direction of increasing $y$. If $d = 2$, it moves $v$ in the direction of decreasing $x$. If $d = 3$, it moves $v$ in the direction of decreasing $y$.

Items in the box at the starting position of a move cannot be collected. That is, when the car moves from $(s_x, s_y)$ to $(e_x, e_y)$, the box at $(s_x, s_y)$ gives no items, but the box at $(e_x, e_y)$ does.

The car starts at $(1, 1)$ and moves a total of $Q$ times. Given the direction and distance of each move, find the total number of items collected over the $Q$ moves.

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

The next $N$ lines each contain three integers $x_i$, $y_i$, and $w_i$, separated by spaces. This means the $i$-th box is at $(x_i, y_i)$, and passing this position gives $w_i$ items.

The next $Q$ lines each contain two integers $d_j$ and $v_j$, separated by a space. This means the car moves $v_j$ in direction $d_j$.

On the first line, print the total number of items collected over the $Q$ moves.

• $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 all different.
• At every moment, the $x$ and $y$ coordinates of the car are between $1$ and $200{,}000$, inclusive.
• All given numbers are integers.