cafea

#include <bits/stdc++.h>

using namespace std;
ifstream fin("cafea.in");
ofstream fout("cafea.out");
struct cafea
{
    int kg, pret;
};
cafea v[100005];

int K, S, N;
bool cmp(struct cafea a, struct cafea b)
{
    double r1 = (double)a.pret/(double)a.kg;
    double r2 = (double)b.pret/(double)b.kg;
    return r1 < r2;
}
int fractionalKnapsack(int W, struct cafea arr[], int n)
{
    sort(arr, arr + n, cmp);
    int curWeight = 0;
    int finalvalue = 0;
    for(int i = 0; i < n; i++)
    {
        if (curWeight + arr[i].kg <= W)
        {
            curWeight += arr[i].kg;
            finalvalue += arr[i].pret;
        }
        else
        {
            int remain = W - curWeight;
            int pr=(arr[i].pret*remain)/arr[i].kg;
            if((arr[i].pret*remain)%arr[i].kg)
                pr++;
            finalvalue += pr;
            break;
        }
    }
    return finalvalue;
}
int main()
{
    fin>>K>>S>>N;
    for(int i=0; i<N; ++i)
        fin>>v[i].kg>>v[i].pret;
    int fsol=fractionalKnapsack(K,v,N);
    if(S>=fsol)
        fout<<S-fsol;
    else
        fout<<0;
    return 0;
}