CBUYING spoj – Chocolate Buying

Nguồn đề bài: http://vn.spoj.com/problems/CBUYING/

1. Đề bài CBUYING spoj

Những con bò rất thích ăn Sô-cô-la , nên Farmer John quyết định mua một ít cho chúng.

Cửa hàng có N loại sô-cô-la (được đánh số từ 1..N) với số lượng mỗi loại không hạn chế. Loại thứ i có giá P_i($$) và có đúng C_i con bò muốn ăn loại Sô-cô-la ấy. Farmer John có B $$ để mua Sô-cô-la cho lũ bò.

Hỏi số bò tối đa mà Farmer John có thể phục vụ là bao nhiêu ? Biết rằng mỗi con bò chỉ thích một loại sô-cô -la, và nó chỉ được ăn loại sô-cô-la ấy.

Input

Dòng đầu tiên là hai số nguyên N và B.

N dòng tiếp theo , dòng thứ i+1 là hai số nguyên dương P_i và C_i.

Output

Gồm một số duy nhất là kết quả.

Example

Input:
5 50
5 3
1 1
10 4
7 2
60 1

Output:
8

Giới hạn

1<=N<=10^5
1 <= B <= 10^18
1 <= C_i <= 10^18
1 <= P_i <= 10^18.

Giải thích:
FJ sẽ mua như sau:
+Mua 3 gói sô-cô-la loại 1 mất 3*5= 15$.
+Mua 1 gói sô-cô-la loại 2 mất 1*1= 1$.
+Mua 2 gói sô-cô-la loại 3 mất 2*10= 20$
+Mua 2 gói sô-cô-la loại 4 mất 2*7= 14$.
Tổng cộng hết :15+1+20+14=50$, và FJ đã phục vụ được 8 con bò.

###################################################

2. Hướng dẫn CBUYING spoj

– Bạn sẽ dễ dàng nhận thấy, cứ ưu tiên mua cho những con bò có bánh yêu thích rẻ hơn thì bạn sẽ được khoản còn lại nhiều hơn. chính vì vậy ở đây chỉ cần sắp xếp C[i], P[i] theo P[i] là được. Tức là ưu tiên mua bánh giá rẽ trước 😀

– còn lại chỉ là tìm cách duyệt lấy kết quả thôi. các bạn có thể tham khảo cách mình viết.

3. Code tham khảo CBUYING spoj

const   fi='';
type    data=longint;
var
        f:text;
        B:qword;
        N:data;
        C,P:array[0..100000+1] of qword;

procedure docfile;
var     i,j:data;
begin
        assign(f,fi); reset(f);
        readln(f,n,b);
        for i:=1 to n do
                readln(f,p[i],c[i]);
        close(f);
end;

procedure sort(l,r: longint);
      var
         i,j: longint;
         x,y:qword;
      begin
         i:=l;
         j:=r;
         x:=p[(l+r) div 2];
         repeat
           while p[i]<x do inc(i);
           while x<p[j] do dec(j);
           if not(i>j) then
             begin
                y:=p[i]; p[i]:=p[j]; p[j]:=y;
                y:=c[i]; c[i]:=c[j]; c[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

procedure xuli;
var     i,j:data;
        res:qword;
begin
        res:=0;
        for i:=1 to n do
                begin
                        if b div p[i]>=c[i] then
                                begin
                                        B:=B-(p[i]*c[i]);
                                        res:=res+c[i];
                                end
                        else
                                begin
                                        res:=res+b div p[i];
                                        break;
                                end;
                end;
        writeln(res);
end;

begin
        docfile;
        sort(1,n);
        xuli;
end.