#P18405. Partially Free Meal
Partially Free Meal
Partially Free Meal
Byteland 新开了一家餐馆。为了吸引顾客,餐馆推出了“部分免费”的活动。
餐馆出售 种菜,编号为 ,每种菜至多点一次。第 种菜的基础价格为 美元,活动价格为 美元。
假设你点了恰好 种菜,编号依次为 ,其中 ,且 ,则实际需要支付的总金额为
$$\sum_{i=1}^{k}a_{p_i}+\max_{1\le i\le k}\{b_{p_i}\}.$$你是这家餐馆的顾客。对于每一个 ,请分别求出点恰好 种菜时,可能支付的最少金额。
输入格式
第一行包含一个整数 (),表示菜的种类数。
接下来 行,每行包含两个整数 (),分别表示第 种菜的基础价格和活动价格。
输入只有一组数据。
输出格式
输出 行。第 行()输出一个整数,表示点恰好 种菜时的最少支付金额。
样例
3
2 5
4 3
3 7
7
11
16