Background

• Prerequisite knowledge: Projectile motion
  (If you do not want to do this after seeing it, you can directly move on to the next problem.)

"Those damn aliens must be here to seize new mineral resources!"
"What the heck is this missile? I cannot figure it out."
Countless droplet-shaped weapons fall from beyond the sky, striking ignorant life fiercely.

Problem Description

After research, the weapon works as follows. Let the direction of gravity be the negative half-axis of the $y$ axis, let the $x$ axis be the ground, and define velocity to the right as positive and to the left as negative.

• Each missile is released and hovers at $(x_i, y_i)$, with initial velocity set to $v_i$.
• After all missiles have been released, they all start projectile motion at the same moment according to their initial velocities. Here $g=9.8$.
• When a missile collides with another missile, it will not change its original trajectory, and its explosive power $p_i$ increases by $1$. Initially, all missiles have $p_i=0$. A collision when touching the $x$ axis also increases the power.
• When a missile reaches the $x$ axis, it deals $p_i$ points of damage to its landing point.

The ground command predicted the landing points of the missiles in advance and deployed countermeasure weapons. The $i$-th weapon can reduce the power value of the $i$-th missile by $a_i$ after it lands (reducing it to at least $0$). However, due to technical limitations, only $m$ countermeasure weapons can be activated. The commander wants to know what the minimum possible total explosive power value of all missiles is.

Input Format

Read from standard input.

The input contains a total of $n+2$ lines.

Line $1$ contains two positive integers $n, m$.

Lines $2$ to $n+1$ each contain three integers $x_i, y_i, v_i$, representing the starting coordinates and horizontal velocity of the $i$-th missile.

Line $n+2$ contains $n$ non-negative integers $a_1, a_2, \cdots, a_n$, with meanings as described above.

Output Format

Write to standard output.

Output one line with one non-negative integer, representing the answer.

3 0
1 1 -2
1 2 -1
1 3 1
1 1 1

0

4 1
-3 3 0
1 3 1
4 3 -4
-9 3 -7
1 3 2 3

1

见附件中的 missile3.in

见附件中的 missile3.ans

见附件中的 missile4.in

见附件中的 missile4.ans

Hint

Sample Explanation

• Sample 1 Explanation:

  The explosive power value of each missile is $0$.

• Sample 2 Explanation:

  The explosive power values of the four missiles are $0, 1, 1, 0$. Activate the $2$-nd or the $3$-rd countermeasure weapon, and the final sum of explosive power values is $1$.

• Sample 4 Note:

  This sample satisfies the constraints of test points $13\sim16$.

Constraints

For $100\%$ of the data, $1 \le n \le 5 \times 10^5$, $0 \le a_i, m \le n$, $0 \le |x_i|, y_i \le 10^9$, $0 \le |v_i| \le 10^6$.

It is guaranteed that all missiles have distinct starting coordinates.

Special property: it is guaranteed that all $y_i$ are the same.

Hint

This problem has a large amount of I/O, so a faster I/O method is recommended.

Landing point formula for projectile motion:

Translated by ChatGPT 5