3605: 糖果-训练套题T4T2

2. 糖果 [cbuying.pas/ c/cpp]

【问题描述】

有N(1≤N~<100,000)种不同类型的糖果，每种糖果数量无限多。第i种糖果每颗的价格是P_i(1≤P_i≤10^18)，有C_i (1≤C_i≤10^18)头牛想吃这种糖果。

    Farmer John拥有金钱B元(1≤B≤10^18)给奶牛们买糖果。他最多可以给多少头牛买到糖果?所有的奶牛都只吃它喜欢的类型的一颗糖果。

  例如：FJ有50块钱，有5种不同类型的糖果：

  糖果类型    每颗糖果价格  想吃该类型糖果的奶牛数量

    1                 5                              3

    2                 1                              1

    3                  10                              4

    4                  7                              2

    5                  60                             1

    显然，FJ不能购买第5种类型的糖果，因为他钱不够。

    下面的购买方案是最优的：

    买1颗类型2的糖果。

    买3颗类型1的糖果。

    买2颗类型4的糖果。

    买2颗类型3的糖果。

    总共花费1+3*5+2*7+2*10=50，这样，FJ最多能满足1+3+2+2=8头牛的糖果需求。

【输入数据】

   第1行：两个整数：N，B。

   第2．．N+1行：每行两个整数：P_i，C_i。

【输出数据】

一行，一个整数，最多可以让多少头奶牛吃到糖果。

【输入样例】

    5  50

    5  3

    1  1

    10 4

    7  2

    60 1

【输出样例】

8