星环防御工事

Luogu
IDLGP8586
Time1000ms
Memory128MB
DifficultyP2
据观测,一共会有共 $n$ 波小行星群攻击太阳系。每一波攻击有两个属性:$d_i,m_i$,表示第 $i$ 波攻击会在第 $d_i$ 个太阳日发动,小行星群的总质量为 $m_i$。如果不进行精准防御,太阳系或将面临灭顶之灾。于是你的上司将星环防御工事的建设任务交给了你。 准确来讲,星环防御工事每个太阳日最多可以击毁总质量为 $k$ 的小行星。对于某一个在第 $d$ 个太阳日出现的小行星群,如果星环防御工事不能在第 $d$ 或 $d+1$ 个太阳日将其击毁(或者仅能部分击毁),那么该小行星群(或其残余部分)将会被移交给地球和平联合组织 TPC 去处理——你当然不希望到手的美差被别人抢走! 因此你现在想知道,你领导的星环防御工事最多可以击毁多少质量的小行星呢? ## Input 第 $1$ 行共两个整数 $n,k$ ,表示共有 $n$ 波小行星群,每个太阳日最多击毁 $k$ 质量的小行星。 第 $2\sim n+1$ 行每行两个非负整数 $d_i,m_i$,含义见题目描述。 ## Output 共一行一个整数 $ans$ ,表示最多可以击毁多少的小行星总质量。 [samples] ## Background 来自河外星系的小行星群即将有组织地打击地球。 ## Note 对于 $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$。
Samples
Input #1
3 3 
1 6
4 7
2 2
Output #1
14
Input #2
10 100
6 14
2 92
3 91
4 74
7 75
2 90
7 25
1 92
3 41
2 14
Output #2
580
API Response (JSON)
{
  "problem": {
    "name": "星环防御工事",
    "description": {
      "content": "据观测,一共会有共 $n$ 波小行星群攻击太阳系。每一波攻击有两个属性:$d_i,m_i$,表示第 $i$ 波攻击会在第 $d_i$ 个太阳日发动,小行星群的总质量为 $m_i$。如果不进行精准防御,太阳系或将面临灭顶之灾。于是你的上司将星环防御工事的建设任务交给了你。 准确来讲,星环防御工事每个太阳日最多可以击毁总质量为 $k$ 的小行星。对于某一个在第 $d$ 个太阳日出现的小行星群,如果星",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8586"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "据观测,一共会有共 $n$ 波小行星群攻击太阳系。每一波攻击有两个属性:$d_i,m_i$,表示第 $i$ 波攻击会在第 $d_i$ 个太阳日发动,小行星群的总质量为 $m_i$。如果不进行精准防御,太阳系或将面临灭顶之灾。于是你的上司将星环防御工事的建设任务交给了你。\n\n准确来讲,星环防御工事每个太阳日最多可以击毁总质量为 $k$ 的小行星。对于某一个在第 $d$ 个太阳日出现的小行星群,如果星...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments