Magry猎奇的省钱策略

时间限制: 1000 ms 内存限制: 65536 kb

总通过人数: 0 总提交人数: 0

题目描述

Magry猎奇的省钱策略有一百种，你想都想不到。

他去了超市买了一堆东西，然后在收银台结帐。然而Magry并不会老老实实把所有的东西都乖乖结帐，而是早早处心积虑想到了这么一个好（馊）主意：

在收银员专注在商品上的时候，可以出其不意偷走一些东西。

已知：Magry的购物车总共有$n$件商品，每件商品价格为$c_{i}$，另外这位收银员会专注于这件商品$t_{i}$秒钟，Magry偷商品的时间为每件1秒。

重要的是，结帐的顺序由Magry决定。

求：Magry这一次购物最少花多少钱？

多组测试数据。

每组数据第一行为1个正整数$n$，表示$n$件商品。$1 \leq n \leq 2000$

接下来n行，每行2个整数$c_{i}$, $t_{i}$（其中$i$代表第$i$件商品），分别代表商品的价值和收银员专注于这件商品的时间。$1 \leq c_{i} \leq 10^{9}$，$0 \leq t_{i} \leq 2000$

需要特别注意的是，如果 $t_{i}=0$，则代表在收银员在专注于这件商品的时候Magry没法偷走任何东西。

对于每组数据，输出一行，Magry的最小花费。