#382. C - 购买零食

C - 购买零食

C - 购买零食

题目描述

高桥去超市购买零食。超市销售 NN 种零食,编号为 11 到 NN。

第 ii 种零食有 AiA_i 件库存,每购买一件可以获得 BiB_i 的满足感。

高桥打算恰好购买 KK 件零食。设 xix_i 为购买第 ii 种零食的数量,需要同时满足:

  • 对所有 1≤i≤N1\le i\le N,都有 0≤xi≤Ai0\le x_i\le A_i;
  • x1+x2+⋯+xN=Kx_1+x_2+\cdots+x_N=K。

总满足感为:

x1B1+x2B2+⋯+xNBNx_1B_1+x_2B_2+\cdots+x_NB_N

请计算满足条件时的最大总满足感。若无法恰好购买 KK 件,则输出 -1。

输入格式

第一行输入两个整数 N,KN,K。

接下来 NN 行,每行输入两个整数 Ai,BiA_i,B_i,分别表示库存数量和购买一件的满足感。

输出格式

输出最大总满足感;若无解,输出 -1。

注意:答案可能达到 101810^{18},需要使用 64 位整数。

数据范围

  • 1≤N≤2×1051\le N\le2\times10^5
  • 1≤K≤1091\le K\le10^9
  • 1≤Ai≤1091\le A_i\le10^9
  • 1≤Bi≤1091\le B_i\le10^9
  • 所有输入均为整数。

样例输入 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