Problem Background

• Prerequisite knowledge: Horizontal Projectile Motion
  (If you see this and don't want to proceed, you can move on to the next question)

"These damn aliens must be here to steal the new mineral resources!"
"What kind of missile is this, I can't figure it out."
Countless teardrop-shaped weapons are falling from beyond the sky, striking down the ignorant lives.

Problem Description

After research, the operation of this weapon is as follows. Gravity is set in the negative direction of the $y$-axis, the $x$-axis represents the ground, and velocity is positive to the right and negative to the left.
- Each missile is deployed and hovers at $(x_i, y_i)$ with an initial velocity of $v_i$.
- After all missiles are deployed, they start to move in horizontal projectile motion with their initial velocities at the same time, where $g = 9.8$.
- When a missile collides with another, it does not change its original path and increases its explosive power $p_i$ by 1. All missiles initially have $p_i = 0$, and collisions upon touching the $x$-axis also increase power.
- When a weapon hits the $x$-axis, it inflicts $p_i$ points of damage at the impact point.

The ground command center has predicted the landing points of the missiles and deployed countermeasures. The $i$-th countermeasure can reduce the power value of the $i$-th missile by $a_i$ (at most to 0) after it lands. However, due to technical limitations, only $m$ countermeasures can be activated. The ground commander wants to know the minimum total explosive power value of the missiles.

Input Format

Input is read from standard input.

The input consists of $n + 2$ lines.

The first line 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.

The $(n + 2)$-th line contains $n$ non-negative integers $a_1, a_2, \cdots, a_n$, as described in the problem statement.

Output Format

Output is written to standard output.

Output a single non-negative integer, which is the answer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

0

Sample Input #2

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

Sample Output #2

1

Sample Input #3

See attached file missile3.in

Sample Output #3

See attached file missile3.ans

Sample Input #4

See attached file missile4.in

Sample Output #4

See attached file missile4.ans

Notes/Hints

[Sample Explanation]

• Sample 1 Explanation:

  Each missile's explosive power value is 0.
  - Sample 2 Explanation:

  The explosive power values of the four missiles are 0, 1, 1, 0 respectively. Activating the 2nd or 3rd countermeasure results in a total explosive power value of 1.

• Sample 4 Explanation:

This sample meets the constraints of test points 13 through 16.

[Data Range]

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$.

All initial coordinates of the missiles are guaranteed to be unique.

Special Property: All $y_i$ are the same.

[Hint]

This problem has a large I/O volume, and it is recommended to use fast I/O methods.

Attached formula for the landing point of horizontal projectile motion:
$$x_t = x_i + v_i \sqrt{\dfrac{2y_i}{g}}$$

见题面 Input 部分

见题面 Output 部分