← 返回题目列表

Codeforces · 19/B

B. 结账助手

中文机器翻译题面 查看原题

Bob来到一家现购自运商店,将n件商品放入手推车中,然后前往收银台付款。每个商品都由其价格 ci 和结账助理在该商品上花费的时间 ti(以秒为单位)来描述。当收银员忙于处理某些物品时,鲍勃可以从他的手推车中偷走一些其他物品。鲍勃要偷一件物品正好需要 1 秒。鲍勃必须向收银员支付的最低金额是多少?请记住,是鲍勃决定结帐助理的商品顺序。

输入

第一个输入行包含数字 n (1 ≤ n ≤ 2000)。在以下 n 行的每一行中,每个项目由一对数字 ti、ci (0 ≤ ti ≤ 2000, 1 ≤ ci ≤ 109) 描述。如果 ti 为 0,Bob 将无法偷任何东西,而结账助理则忙着处理物品 i。

输出

输出一个数字 — 回答问题:鲍勃必须支付的最低金额是多少。

示例

输入 #1

4
2 10
0 20
1 5
1 3

输出 #1

8

输入 #2

3
0 1
0 10
0 100

输出 #2

111