题目背景

为了对付A国，B国研制了激光武器。

题目描述

自然，激光武器需要发射源才能运作。B国已经在距地面 $H$ 处放了 $n$ 个发射源,准备向地面发射激光。

我们不妨设x轴为地面，y轴方向为竖直方向。

对于第 $i$ 个发射源，它位于 $(x_i , H)$ 处 ， 发射的方向的方向向量为$(a_i , -1)$ , 在时刻$t_i$时发挥作用。

数据保证发射源的位置不可以重叠

每个发射源只能发射一次激光，且激光持续时间极短，不会影响到下一时刻。

当激光从发射源发出后，这激光的威力值为 $0$ , 但是当两束激光相遇（包括在地面上相遇）时，这两束激光的威力值都增加 $1$ ,它们不会改变原来的运行轨迹

激光相遇定义为，两束激光运行轨迹的两条线段有交点，不考虑激光的速度。

当激光打到地面上时，会造成与其威力值相等的杀伤值。

作为A国指挥官，你已经知道了所有激光的轨迹，并且已经部署了 $n$ 个能量盾来反制激光武器。第 $i$ 个能量盾可以减少第 $i$ 个发射源发出的激光 $d_i$ 点威力值(最多把这个激光的威力降低到0)。但是由于能量不足，你总共只能开 $m$ 个能量盾。请通过合理的部署，将激光造成的杀伤总值降到最低。

能量盾与激光是一一对应的，第 $i$ 个能量盾只能应对第 $i$ 个发射源发射的激光,不会对其他激光造成任何影响

输入格式

第一行三个数 $n ,m ,H$

第 $2$ 行至第 $n+1$ 行每行3个数 $x_i , a_i , t_i$

最后一行 $n$个数 ， $d_i$

输出格式

一个整数 ，在经过最佳的能量盾部署后，激光造成的杀伤总值

数据范围

对于 $50%$ 的数据 ， $n <= 1000$

对于 $100%$ 的数据 ，$m <= n <= 500000 , H <= 10^3 , |x_i| <= 10^9 , |a_i| <= 10^6 , d_i <= n，0 < t_i <= 10^9$

注意， $x_i$ 可能为负

样例1

输入

5 2 1
0 1 1
1 1 1
2 1 1
3 1 1
4 -4 1
3 3 3 3 3

输出

4

样例解释

第 $1,2,3,4$ 根激光分别与第 $5$ 根激光相遇 ，所以他们的威力值为 $1,1,1,1,4$. 开启第4个和第5个能量盾，剩下的威力值和为 $1+1+1+0+1 = 4$

样例2

输入

6 2 2
1 1 1
8 0 2
2 1 1
3 0 1
114 -514 1
9 -1 2
0 0 0 0 1 1

输出

10