[COCI 2012/2013 #2] POPUST

Luogu

IDLGP8298

Time2000ms

Memory32MB

DifficultyP4

贪心2012COCI（克罗地亚）

Mirko 像熊一样饥饿，发现了一家当地餐馆。这家餐厅提供 $N$ 顿饭，并且有一个有趣的定价政策：每顿饭都有两个指定价格，$A_i$ 和 $B_i$。Mirko 点的第一道菜只需要付 $A$ 元，其他菜都需要付 $B$ 元。 Mirko 无法决定点多少菜。为了更简单地作出决定，他向你求助。对于任意 $k\in[1,N]$，点 $k$ 道菜最少要付的钱。Mirko 不在乎他点了哪些特别的饭菜，也不管他点菜的顺序，但他不会点两道同样的菜。 ## Input 第一行一个正整数 $N\ (2\le N\le 5\times 10^5)$，表示菜品数量。接下来 $N$ 行，每行两个正整数 $A_i,B_i\ (1\le A_i,B_i\le 10^9)$，题目已经描述。 ## Output 输出包含 $N$ 行，第 $k$ 行表示点 $k$ 道互不相同的菜最少需要花多少钱。 [samples] ## Background **本题分值按 COCI 原题设置，满分 $120$。** ## Note #### 样例#1 解释/说明 - $k=1$: Mirko 开始点第 $2$ 道菜，共花费 $A_2=9$ 元。 - $k=2$: Mirko 开始点第 $1$ 道菜，接着点第 $2$ 道菜，共花费 $A_1+B_2=13$ 元。 - $k=3$: Mirko 开始点第 $1$ 道菜，接着点第 $2,3$ 道菜，共花费 $A_1+B_2+B_3=18$ 元。

Samples

Input #1

Output #1

9
13
18

Input #2

2
100 1
1 100

Output #2

1
2

Input #3

5
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2012/2013 #2] POPUST",
    "description": {
      "content": "Mirko 像熊一样饥饿，发现了一家当地餐馆。这家餐厅提供 $N$ 顿饭，并且有一个有趣的定价政策：每顿饭都有两个指定价格，$A_i$ 和 $B_i$。Mirko 点的第一道菜只需要付 $A$ 元，其他菜都需要付 $B$ 元。 Mirko 无法决定点多少菜。为了更简单地作出决定，他向你求助。对于任意 $k\\in[1,N]$，点 $k$ 道菜最少要付的钱。Mirko 不在乎他点了哪些特别的饭菜，也",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 32768
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8298"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mirko 像熊一样饥饿，发现了一家当地餐馆。这家餐厅提供 $N$ 顿饭，并且有一个有趣的定价政策：每顿饭都有两个指定价格，$A_i$ 和 $B_i$。Mirko 点的第一道菜只需要付 $A$ 元，其他菜都需要付 $B$ 元。\n\nMirko 无法决定点多少菜。为了更简单地作出决定，他向你求助。对于任意 $k\\in[1,N]$，点 $k$ 道菜最少要付的钱。Mirko 不在乎他点了哪些特别的饭菜，也...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments