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