UVA1336 修缮长城 Fixing the Great Wall

为了简化这个问题，我们把长城看成是一条直线，每个需要修补的点都被用它离起点的距离（一个整数）标记了。GWARR被放在长城的一个随机位置上，并且可以以恒定的速度双向移动。每个点距离起点的距离，现在立即修复的花费，以及每过单位时间修复花费的增长量都已知。GWARR的工作效率极高，以至于它可以立即修复好经过的需要修复的地方。

输入包含多组测试数据。每组测试数据的格式如下： 第一行包含$3$个整数$N, V, X$，分别表示点的数量，GWARR的移动速度，GWARR的出发点位置。 接下来$n$行，每行$3$个整数$x,c,\Delta$，表示这个点的位置，现在立即修复的花费，以及每过单位时间修复花费的增长量。保证没有两个点的位置相同。 输入以一行$N=V=X=0$作为结束标记。

$N$行，每行一个整数，表示每组数据的最小总花费（**向下取整**），保证输出结果不超过$10^9$。 ## 样例输入输出 ### 样例输入\#1： 3 1 1000 1010 0 100 998 0 300 996 0 3 3 1 1000 1010 0 100 998 0 3 996 0 3 0 0 0 ### 样例输出\#1： 2084 1138 ### 样例输入输出解释： 对于第一种情况，我们选择先修复距离$998$处，花费$600$，然后是$1010$处，花费$1400$，然后是$996$处，花费$84$。合计$2084$。 由 @Sparky_14145 提供翻译

对于$100 \%$数据有： $1 \leq N \leq 1000, 1 \leq V \leq 100,1 \leq X \leq 500,000$； $1 \leq x \leq 500,000, 1 \leq c \leq 50,000, 1 \leq \Delta \leq 50,000$。