No.1726 [Cherry 3rd Tune B] Jamaica Beer Pong
Problem Statement
There are $N$ cups (filled with beer) on the coordinate plane. Here, the $i~(1 \leq i \leq N)$-th cup is located at coordinates $(a_i, b_i)$, and an integer $P_i$ is assigned to it.
Cherry-chan will throw $M$ ping-pong balls, and thanks to your precognitive ability, you know that the $j~(1 \leq j \leq M)$-th ping-pong ball will land at coordinates $(c_j, d_j)$. A ping-pong ball enters the cup at the coordinates where it lands if and only if there is a cup at those coordinates.
Before Cherry-chan throws the $M$ ping-pong balls, you may repeat the following operations $0$ or more times, as many times as you like and in any order.
- Choose a real number $p$, and move all cups to their positions symmetric with respect to the line $x=p$.
- Choose a real number $q$, and move all cups to their positions symmetric with respect to the line $y=q$.
Here, the coordinates where the ping-pong balls land are not affected by the operations.
After Cherry-chan has thrown the $M$ ping-pong balls, the score is the sum of the integers assigned to the cups containing a ping-pong ball.
Find the score obtained when you perform operations so as to maximize the score.
Constraints
- $1 \leq N,M \leq 800$
- $-10^6 \leq P_i \leq 10^6$
- $-10^9 \leq a_i, b_i, c_j, d_j \leq 10^9$
- If $i \neq i'$, then $(a_i, b_i) \neq (a_{i'}, b_{i'})$
- If $j \neq j'$, then $(c_j, d_j) \neq (c_{j'}, d_{j'})$
- All inputs are integers.
Input
The input is given from standard input in the following format.$N$ $M$ $P_1$ $\cdots$ $P_N$ $a_1$ $b_1$ $\vdots$ $a_N$ $b_N$ $c_1$ $d_1$ $\vdots$ $c_M$ $d_M$
Output
Output the maximum score as an integer. Print a newline at the end.
Sample
Sample 1
Input
2 2 3 1 0 0 1 0 2 2 4 1
Output
3
Let us call the two cups cup A and cup B, respectively. Perform the operation three times as follows.
- Reflect the cups with respect to $x=-2$. Cup A moves to $(-4,0)$ and cup B moves to $(-5,0)$.
- Reflect the cups with respect to $y=\frac{1}{2}$. Cup A moves to $(-4,1)$ and cup B moves to $(-5,1)$.
- Reflect the cups with respect to $x=0$. Cup A moves to $(4,1)$ and cup B moves to $(5,1)$.
Then, of the $2$ ping-pong balls thrown by Cherry-chan, the $2$nd ping-pong ball enters cup A. Since the integer assigned to cup A is $3$, the score is $3$ points.
Moreover, no matter how you perform the operations, the score cannot exceed $3$ points, so the answer is $3$.
Sample 2
Input
3 3 100 20 3 0 0 -1 0 -1 1 0 0 1 0 1 1
Output
123
A score of $123$ points can be achieved by performing a reflection with respect to $x=0$. Note that there may exist integers $i,j$ such that $(a_i, b_i)=(c_j, d_j)$ in the initial state.
Sample 3
Input
3 2 -1 -2 -4 1 1 2 4 3 9 4 16 5 25
Output
0
If even one ping-pong ball enters a cup, the score becomes negative.
Sample 4
Input
20 24 -10 10 9 4 -3 10 7 4 6 -6 3 6 -10 3 1 -4 10 5 -10 -8 0 2 2 2 1 0 -1 -2 -1 -1 -2 -1 0 -1 0 -2 0 1 2 -1 1 2 2 1 -2 0 -2 2 0 0 1 1 2 0 1 -2 1 -1 -1 2 3 -1 3 1 2 2 1 3 -2 -2 -1 -2 -2 -1 -2 1 -1 1 3 -3 3 3 0 -2 0 1 2 -1 -1 -3 -2 -3 -1 3 -3 -1 0 0 2 -3 1 1 0 3 1 -2 -2 2
Output
56
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun
tatyam