C - 购买零食
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
C - 购买零食
题目描述
高桥去超市购买零食。超市销售 种零食,编号为 到 。
第 种零食有 件库存,每购买一件可以获得 的满足感。
高桥打算恰好购买 件零食。设 为购买第 种零食的数量,需要同时满足:
- 对所有 ,都有 ;
- 。
总满足感为:
请计算满足条件时的最大总满足感。若无法恰好购买 件,则输出 -1。
输入格式
第一行输入两个整数 。
接下来 行,每行输入两个整数 ,分别表示库存数量和购买一件的满足感。
输出格式
输出最大总满足感;若无解,输出 -1。
注意:答案可能达到 ,需要使用 64 位整数。
数据范围
- 所有输入均为整数。
样例输入 1
3 5
3 10
4 20
2 15
样例输出 1
95
样例输入 2
2 10
3 5
4 8
样例输出 2
-1
样例输入 3
6 30
8 12
5 25
10 7
4 30
12 18
6 15
样例输出 3
587
样例输入 4
10 500000000
100000000 800000000
50000000 950000000
120000000 400000000
80000000 1000000000
200000000 600000000
90000000 300000000
150000000 750000000
60000000 850000000
70000000 500000000
110000000 200000000
样例输出 4
407000000000000000
样例输入 5
1 1
1 1
样例输出 5
1