{"raw_statement":[{"iden":"background","content":"- 前置芝士：[平抛运动](https://baike.baidu.com/item/%E5%B9%B3%E6%8A%9B%E8%BF%90%E5%8A%A8/974021?fr=aladdin)\n~~（看到这个如果不想做可以直接开下一题）~~\n\n「这群该死的外星人，肯定是来抢夺新矿资源的！」  \n「这导弹什么鬼啊，研究不明白。」  \n无数的水滴型武器从苍穹之外落下，猛击着无知的生命。  "},{"iden":"statement","content":"经研究，该武器的运作方式是这样的。其中设重力方向为 $y$ 轴负半轴，$x$ 轴为地面，速度向右为正向左为负。  \n- 每颗导弹在 $(x_i,y_i)$ 的地方投放并悬浮，初始速度设置为 $v_i$。\n- 所有导弹投放完成后，于同一时刻开始照初始速度做平抛运动。其中 $g=9.8$。  \n- 每颗导弹与另一颗导弹碰撞时，不会改变原来的路线，并且将爆破威力 $p_i$ 增加 $1$，所有导弹初始时 $p_i=0$，**在接触到 $x$ 轴时碰撞也增加威力**。\n- 当武器落到 $x$ 轴时，会对落点造成 $p_i$ 点杀伤力。\n\n地面指挥部提前预测了导弹的落点，并部署了反制武器。第 $i$ 台武器能将第 $i$ 枚导弹在降落至地面后的威力值减少 $a_i$（至多减少到 $0$）。但是，由于技术限制，只能启动其中 $m$ 台反制武器。地面指挥官想知道，导弹造成的爆炸威力值总和最小为多少。"},{"iden":"input","content":"从标准输入中读入数据。\n\n输入一共包含 $n+2$ 行。\n\n第 $1$ 行输入两个正整数 $n,m$。\n\n第 $2$ 行到第 $n+1$ 行每行包含三个整数 $x_i,y_i,v_i$，表示第 $i$ 颗导弹的起点坐标和水平速度。 \n\n第 $n+2$ 行包含 $n$ 个非负整数 $a_1,a_2,\\cdots,a_n$，含义见题目描述。"},{"iden":"output","content":"输出到标准输出。\n\n输出一行一个非负整数，表示答案。"},{"iden":"note","content":"**【样例解释】**\n\n- **样例 1 解释：** \n\n\t每颗导弹的爆炸威力值都是 $0$。\n- **样例 2 解释：** \n\n\t四枚导弹的爆炸威力值分别是 $0,1,1,0$，启动第 $2$ 或第 $3$ 台反制武器，最后爆炸威力值的和为 $1$。\n    \n- **样例 4 说明：**\n\n   该样例满足测试点 $13\\sim16$ 的限制。\n***\n**【数据范围】**\n\n对于 $100\\%$ 的数据，$1\\le n\\le5\\times10^5$，$0\\le a_i,m\\le n$，$0\\le |x_i|,y_i\\le10^9$，$0\\le |v_i|\\le10^6$。  \n\n**保证所有导弹起始坐标不相等。**\n\n|测试点编号|$n\\le$|特殊性质|\n|:-:|:-:|:-:|\n|$1\\sim6$|$5000$|无|\n|$7\\sim10$|$12000$|无|\n|$11\\sim12$|$10^5$|有|\n|$13\\sim16$|$10^5$|无|\n|$17\\sim20$|$5\\times10^5$|无|\n\n特殊性质：保证所有 $y_i$ 均相同。  \n\n**【提示】**\n\n本题 I/O 量较大，推荐使用较快的 I/O 方式。\n\n附平抛运动落点公式：  \n$$x_t=x_i+v_i\\sqrt{\\dfrac{2y_i}g}$$"}],"translated_statement":null,"sample_group":[["3 0\n1 1 -2\n1 2 -1\n1 3 1\n1 1 1","0"],["4 1\n-3 3 0\n1 3 1\n4 3 -4\n-9 3 -7\n1 3 2 3","1"],["见附件中的 missile3.in","见附件中的 missile3.ans"],["见附件中的 missile4.in","见附件中的 missile4.ans"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}