P8593 "KDOI-02" A Projectile Throw

- Prerequisite knowledge: [Projectile motion](https://baike.baidu.com/item/%E5%B9%B3%E6%8A%9B%E8%BF%90%E5%8A%A8/974021?fr=aladdin) ~~(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.

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.

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.

Write to standard output. Output one line with one non-negative integer, representing the answer.

**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.** |Test Point ID|$n \le$|Special Property| |:-:|:-:|:-:| |$1\sim6$|$5000$|None| |$7\sim10$|$12000$|None| |$11\sim12$|$10^5$|Yes| |$13\sim16$|$10^5$|None| |$17\sim20$|$5\times10^5$|None| 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: $$x_t=x_i+v_i\sqrt{\dfrac{2y_i}g}$$ Translated by ChatGPT 5