{"raw_statement":[{"iden":"problem statement","content":"Snuke Inc. offers various kinds of services.  \nA payment plan called Snuke Prime is available.  \nIn this plan, by paying $C$ yen (the currency of Japan) per day, you can use all services offered by the company without additional fees.  \nYou can start your subscription to this plan at the beginning of any day and cancel your subscription at the end of any day.\nTakahashi is going to use $N$ of the services offered by the company.  \nHe will use the $i$\\-th of those services from the beginning of the $a_i$\\-th day until the end of the $b_i$\\-th day, where today is the first day.  \nWithout a subscription to Snuke Prime, he has to pay $c_i$ yen per day to use the $i$\\-th service.\nFind the minimum total amount of money Takahashi has to pay to use the services."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq C \\leq 10^9$\n*   $1 \\leq a_i \\leq b_i \\leq 10^9$\n*   $1 \\leq c_i \\leq 10^9$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $C$\n$a_1$ $b_1$ $c_1$\n$\\vdots$\n$a_N$ $b_N$ $c_N$"},{"iden":"sample input 1","content":"2 6\n1 2 4\n2 2 4"},{"iden":"sample output 1","content":"10\n\nHe will use the $1$\\-st service on the $1$\\-st and $2$\\-nd days, and the $2$\\-nd service on the $2$\\-nd day.  \nIf he subscribes to Snuke Prime only on the $2$\\-nd day, he will pay $4$ yen on the $1$\\-st day and $6$ yen on the $2$\\-nd day, for a total of $10$ yen.  \nIt is impossible to make the total payment less than $10$ yen, so we should print $10$."},{"iden":"sample input 2","content":"5 1000000000\n583563238 820642330 44577\n136809000 653199778 90962\n54601291 785892285 50554\n5797762 453599267 65697\n468677897 916692569 87409"},{"iden":"sample output 2","content":"163089627821228\n\nIt is optimal to do without Snuke Prime."},{"iden":"sample input 3","content":"5 100000\n583563238 820642330 44577\n136809000 653199778 90962\n54601291 785892285 50554\n5797762 453599267 65697\n468677897 916692569 87409"},{"iden":"sample output 3","content":"88206004785464"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}