{"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 不在乎他点了哪些特别的饭菜，也不管他点菜的顺序，但他不会点两道同样的菜。\n\n## Input\n\n第一行一个正整数 $N\\ (2\\le N\\le 5\\times 10^5)$，表示菜品数量。\n\n接下来 $N$ 行，每行两个正整数 $A_i,B_i\\ (1\\le A_i,B_i\\le 10^9)$，题目已经描述。\n\n## Output\n\n输出包含 $N$ 行，第 $k$ 行表示点 $k$ 道互不相同的菜最少需要花多少钱。\n\n[samples]\n\n## Background\n\n**本题分值按 COCI 原题设置，满分 $120$。**\n\n## Note\n\n#### 样例#1 解释/说明\n\n- $k=1$: Mirko 开始点第 $2$ 道菜，共花费 $A_2=9$ 元。\n\n- $k=2$: Mirko 开始点第 $1$ 道菜，接着点第 $2$ 道菜，共花费 $A_1+B_2=13$ 元。\n\n- $k=3$: Mirko 开始点第 $1$ 道菜，接着点第 $2,3$ 道菜，共花费 $A_1+B_2+B_3=18$ 元。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8298","tags":["贪心","2012","COCI（克罗地亚）"],"sample_group":[["3\n10 5\n9 3\n10 5","9\n13\n18"],["2\n100 1\n1 100","1\n2"],["5\n1000000000 1000000000\n1000000000 1000000000\n1000000000 1000000000\n1000000000 1000000000\n1000000000 1000000000","1000000000\n2000000000\n3000000000\n4000000000\n5000000000"]],"created_at":"2026-03-03 11:09:25"}}