#L8586. 洛谷模拟 星环防御工事(defence)

洛谷模拟 星环防御工事(defence)

星环防御工事

题目背景

来自河外星系的小行星群即将有组织地打击地球。

题目描述

据观测,一共会有共 nn 波小行星群攻击太阳系。每一波攻击有两个属性:di,mid_i,m_i,表示第 ii 波攻击会在第 did_i 个太阳日发动,小行星群的总质量为 mim_i。如果不进行精准防御,太阳系或将面临灭顶之灾。于是你的上司将星环防御工事的建设任务交给了你。

准确来讲,星环防御工事每个太阳日最多可以击毁总质量为 kk 的小行星。对于某一个在第 dd 个太阳日出现的小行星群,如果星环防御工事不能在第 ddd+1d+1 个太阳日将其击毁(或者仅能部分击毁),那么该小行星群(或其残余部分)将会被移交给地球和平联合组织 TPC 去处理——你当然不希望到手的美差被别人抢走!

因此你现在想知道,你领导的星环防御工事最多可以击毁多少质量的小行星呢?

输入格式

11 行共两个整数 n,kn,k ,表示共有 nn 波小行星群,每个太阳日最多击毁 kk 质量的小行星。

2n+12\sim n+1 行每行两个非负整数 di,mid_i,m_i,含义见题目描述。

输出格式

共一行一个整数 ansans ,表示最多可以击毁多少的小行星总质量。

样例 #1

样例输入 #1

3 3 
1 6
4 7
2 2

样例输出 #1

14

样例 #2

样例输入 #2

10 100
6 14
2 92
3 91
4 74
7 75
2 90
7 25
1 92
3 41
2 14

样例输出 #2

580

提示

对于 10%10\% 的数据,1n,max{di}201\leq n,\max\{d_i\} \leq 20

对于 20%20\% 的数据,1n,max{di}6001\leq n,\max\{d_i\}\leq 600

对于 40%40\% 的数据,1n,max{di}50001\leq n,\max\{d_i\}\leq 5000

对于另外 10%10\% 的数据,保证全部小行星群的 mim_i 总和不超过 kk

对于 100%100\% 的数据,1n,max{di}3×1051\leq n,\max\{d_i\}\leq 3\times 10^50mi,k1040\leq m_i,k\leq 10^4