← 返回题目列表

Codeforces · 215/D

D. 炎热的日子

中文机器翻译题面 查看原题

贝尔兰的官方首都和文化首都由一条贯穿n个地区的道路连接起来。每个地区都有独特的气候,因此第 i (1 ≤ i ≤ n) 地区在夏季有稳定的 ti 度温度。

今年夏天,一群 m 名学生想要从官方首都前往文化首都参观博物馆和景点。旅行组织者用公共汽车运送孩子们在城市之间,但有时天气很热。具体来说,如果公交车行驶经过第 i 个区域,并且有 k 个学童,则公交车内的温度为 ti + k 度。

当然,没有人喜欢公共汽车很热。因此,当公交车行驶经过第 i 个区域时,如果车内温度超过 Ti 度,则车上的每个学生都要求对不舒服的情况进行赔偿。补偿金额高达xi卢布,并按车内温度超标的每个地区进行收费。

为了省钱,行程组织者可能会在行程开始时以及区域之间任意添加或删除额外的巴士(当然,他们需要至少一辆巴士才能经过任何区域)。组织者也可以任意将孩子们分类到公共汽车上,但是,第i个区域的每辆公共汽车将花费组织者成本卢布。请注意,将儿童分类送上巴士不需要花钱。

您的任务是找到最少数量的卢布,组织者将不得不花费这些卢布来运送所有学童。

输入

第一输入行包含两个整数 n 和 m (1 ≤ n ≤ 105; 1 ≤ m ≤ 106) — 相应地,途中区域的数量和该组中学童的数量。接下来的 n 行每行包含四个整数:第 i 行包含 ti、Ti、xi 和 costi(1 ≤ ti、Ti、xi、costi ≤ 106)。行中的数字由单个空格分隔。

输出

打印唯一的整数——组织者运送所有学童所需花费的最低卢布数量。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

2 10
30 35 1 100
20 35 10 10

输出 #1

120

输入 #2

3 100
10 30 1000 1
5 10 1000 3
10 40 1000 100000

输出 #2

200065

注意

在第一个示例中,组织者将仅使用一辆巴士穿越第一个区域。然而,车内温度将达到30+10=40度,10名学童将分别要求赔偿。也只有一辆巴士载着这群人穿过第二个区域,但里面的温度不会超过限制。总的来说,组织者将花费100+10+10=120卢布。