CF215D.Hot Days

The official capital and the cultural capital of Berland are connected by a single road running through n regions. Each region has a unique climate, so the i-th (1 ≤ i ≤ n) region has a stable temperature of t__i degrees in summer.

This summer a group of m schoolchildren wants to get from the official capital to the cultural capital to visit museums and sights. The trip organizers transport the children between the cities in buses, but sometimes it is very hot. Specifically, if the bus is driving through the i-th region and has k schoolchildren, then the temperature inside the bus is t__i + k degrees.

Of course, nobody likes it when the bus is hot. So, when the bus drives through the i-th region, if it has more than T__i degrees inside, each of the schoolchild in the bus demands compensation for the uncomfortable conditions. The compensation is as large as x__i rubles and it is charged in each region where the temperature in the bus exceeds the limit.

To save money, the organizers of the trip may arbitrarily add or remove extra buses in the beginning of the trip, and between regions (of course, they need at least one bus to pass any region). The organizers can also arbitrarily sort the children into buses, however, each of buses in the i-th region will cost the organizers cost__i rubles. Please note that sorting children into buses takes no money.

Your task is to find the minimum number of rubles, which the organizers will have to spend to transport all schoolchildren.

伯兰的官方首都与文化首都之间仅由一条穿过 $n$ 个区域的道路连接。每个区域具有独特的气候，因此第 $i$ 个区域（$1 ≤ i ≤ n$）在夏季具有稳定的温度 $t_i$ 摄氏度。

今年夏天，有 $m$ 名中小学生计划从官方首都前往文化首都参观博物馆和景点。活动组织者使用公交车运送这些学生，但有时天气非常炎热。具体而言，若一辆公交车正驶过第 $i$ 个区域，且车内有 $k$ 名学生，则车内的温度为 $t_i + k$ 摄氏度。

显然，没有人喜欢闷热的公交车。因此，当公交车驶过第 $i$ 个区域时，若车内温度超过 $T_i$ 摄氏度，则该公交车内的每名学生都会因不适而要求补偿。每名学生在该区域索取的补偿金额为 $x_i$ 卢布；只要某区域车内温度超标，即在该区域收取补偿。

为节省开支，活动组织者可在行程开始前以及各区域之间任意增减额外的公交车（当然，通过任一区域时至少需有一辆公交车）。组织者还可任意将学生分配至各辆公交车中；但需注意：在第 $i$ 个区域内运行的每辆公交车，其运营成本为 $cost_i$ 卢布。请特别注意：将学生分配至不同公交车的过程本身不产生任何费用。

你的任务是求出组织者运送全部 $m$ 名学生所需的最小卢布总支出。

The first input line contains two integers n and m (1 ≤ n ≤ 105; 1 ≤ m ≤ 106) — the number of regions on the way and the number of schoolchildren in the group, correspondingly. Next n lines contain four integers each: the i-th line contains t__i, T__i, x__i and cost__i (1 ≤ t__i, T__i, x__i, cost__i ≤ 106). The numbers in the lines are separated by single spaces.

第一行输入包含两个整数 $n$ 和 $m$（$1 ≤ n ≤ 10^5$；$1 ≤ m ≤ 10^6$），分别表示路径上的区域数量和小组中学生的数量。接下来的 $n$ 行每行包含四个整数：第 $i$ 行包含 $t_i$、$T_i$、$x_i$ 和 $cost_i$（$1 ≤ t_i,\, T_i,\, x_i,\, cost_i ≤ 10^6$）。同一行中的数字以单个空格分隔。

Print the only integer — the minimum number of roubles the organizers will have to spend to transport all schoolchildren.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

输出唯一的整数——主办方为运送所有学生所需花费的最少卢布数。

请注意，在 C++ 中请勿使用 %lld 说明符来读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 说明符。

In the first sample the organizers will use only one bus to travel through the first region. However, the temperature in the bus will equal 30 + 10 = 40 degrees and each of 10 schoolchildren will ask for compensation. Only one bus will transport the group through the second region too, but the temperature inside won't exceed the limit. Overall, the organizers will spend 100 + 10 + 10 = 120 rubles.

在第一个样例中，组织者将仅使用一辆巴士穿越第一区域。然而，巴士内的温度将达到 $30 + 10 = 40$ 摄氏度，每名学生都将索要补偿。穿越第二区域时同样只使用一辆巴士，但车内温度不会超过限制。总体而言，组织者将花费 $100 + 10 + 10 = 120$ 卢布。