#2193. game

    ID: 2193 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest1648来源:qoj.ac数据:公开样例动态规划

game

game

题目描述

标题: game - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

你最近学习了打隔膜。

有 n 个怪物,击败第 i 个怪物 Ai 点体力,而击败它之后可以获得 Bi 点体力。任意时刻,体力都不能是负数。

对每个 k=1,2,⋯,n,试求出击败 k 个怪物至少需要多少初始体力。

输入格式

第一行一个正整数 n,m,表示怪物个数。

接下来的 n 行,每行两个整数 Ai,Bi,表示怪物的属性。

输出格式

输出一行 n 个非负整数,第 i 个表示击败 i 个怪物所需的最小初始体力。

样例一

input

4
1 2
3 4
1 1
2 3

output

1 2 3 4

样例二

input

8
304 282
773 724
274 481
43 254
813 110
722 107
140 62
351 418

output

43 43 63 63 63 288 341 1044

数据范围与提示

  • 子任务 1(5 分):n≤16。
  • 子任务 2(27 分):n≤7000。
  • 子任务 3(68 分):无特殊限制。

对于 100% 的数据,1≤n≤3×105,1≤Ai,Bi≤109。

时间限制:2s

空间限制:512MB

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4
1 2
3 4
1 1
2 3
1 2 3 4

样例 2

8
304 282
773 724
274 481
43 254
813 110
722 107
140 62
351 418
43 43 63 63 63 288 341 1044