据观测,一共会有共 n 波小行星群攻击太阳系。每一波攻击有两个属性: d_i,m_i ,表示第 i 波攻击会在第 d_i 个太阳日发动,小行星群的总质量为 m_i 。如果不进行精准防御,太阳系或将面临灭顶之灾。于是你的上司将星环防御工事的建设任务交给了你。
准确来讲,星环防御工事每个太阳日最多可以击毁总质量为 k 的小行星。对于某一个在第 d 个太阳日出现的小行星群,如果星环防御工事不能在第 d 或 d+1 个太阳日将其击毁(或者仅能部分击毁),那么该小行星群(或其残余部分)将会被移交给地球和平联合组织 TPC 去处理——你当然不希望到手的美差被别人抢走!
因此你现在想知道,你领导的星环防御工事最多可以击毁多少质量的小行星呢?
第 1 行共两个整数 n,k ,表示共有 n 波小行星群,每个太阳日最多击毁 k 质量的小行星。
第 2\sim n+1 行每行两个非负整数 d_i,m_i ,含义见题目描述。
共一行一个整数 ans ,表示最多可以击毁多少的小行星总质量。
3 3 1 6 4 7 2 2
14
10 100 6 14 2 92 3 91 4 74 7 75 2 90 7 25 1 92 3 41 2 14
580
对于 10\% 的数据, 1\leq n,\max\{d_i\} \leq 20 。
对于 20\% 的数据, 1\leq n,\max\{d_i\}\leq 600 。
对于 40\% 的数据, 1\leq n,\max\{d_i\}\leq 5000 。
对于另外 10\% 的数据,保证全部小行星群的 m_i 总和不超过 k 。
对于 100\% 的数据, 1\leq n,\max\{d_i\}\leq 3\times 10^5 , 0\leq m_i,k\leq 10^4 。