問題一覧 > 通常問題

No.1726 [Cherry 3rd Tune B] Jamaica Beer Pong

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 42
作問者 : 👑 Kazun / テスター : tatyam nebocco
お気に入りにしたユーザー ProblemId : 6065 / 自分の提出
問題文最終更新日: 2021-10-29 19:44:47
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 320 (Stray Bullet) (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。