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