The Great Wall of China is truly one of the greatest wonders of the world. In 3-rd century BC, Emperor Qin Shi Huang connected the defensive structures built earlier by the states of Qin, Yan, and Zhao kingdoms. The purpose of the wall was to defend against raids by the barbarians from Mongolia and Manchuria. The wall was extended and renovated in later centuries, creating an impressive 6,700 km long fortification. The centuries have left their mark on the wall, there are several sections that need immediate renovation. These sections have to be repaired as soon as possible since they deteriorate every day: if we do not fix them now, it will be more expensive to repair them later. Thus the Ministry of Monuments have designed and built the world’s first Great Wall Automatic Repair Robot (GWARR), to repair the damaged sections (we are in the 21-st century, aren’t we?) Your task is to write the software that will guide the robot and decide the order in which the sections are to be repaired. For the purpose of this problem, we assume that the Great Wall is a long straight line, and every location on the wall is identified by a single number (say, the distance from one end). The GWARR is placed at some location on the wall and it can move with constant speed in both directions. For each damaged section you are given its location, how much it would cost to repair now, and how the cost would increase if repaired later. The GWARR works so efficiently that once it is at the exact location of the damaged section it can repair the wall immediately. Input The input contains several blocks of test cases. Each case begins with a line containing three integers: an integer 1 ≤ n ≤ 1000, the number of damaged sections, an integer 1 ≤ v ≤ 100, the speed of the GWARR in distance units/time units, and an integer 1 ≤ x ≤ 500000, the initial position of the GWARR. The next n lines describe the n damaged sections that have to be repaired. Each line contains three integers: the location 1 ≤ x ≤ 500000 of the section, the cost 0 ≤ c ≤ 50000 of repairing it immediately, and 1 ≤ ∆ ≤ 50000, the increase in cost per time unit. Therefore, if the section is repaired after t time units have passed, then we have to pay c + t∆ units of money. It can be assumed that the locations of the sections are all different, and the initial location of the robot is not on the list of damaged seetions. The input is terminated by a test case with n = v = x = 0. Output For each test case, you have to output a line containing a single number, the minimum cost of repairing the wall. This number should be an integer, round down the result, if necessary. It can be assumed that the minimum cost is not more than 1000000000. In the optimum solution for the first test case below, we first fix loeation 998 at the cost of 600, then the location 1010 at the cost of l400, and finally we fix the location 996 at the cost of 84, giving the total cost 2084. Sample Input 3 1 1000 1010 0 100 998 0 300 996 0 3
2/2 3 1 1000 1010 0 100 998 0 3 996 0 3 000 Sample Output 2084 1138