Mixing Milk


/*
ID: tausiq11
PROG: milk
LANG: C++
*/

#include <stdio.h>
#include <algorithm>
using namespace std;

struct node {
    int charge;
    int amount;
} a [5002];

int main ()
{
    freopen ("milk.in", "r", stdin);
	freopen ("milk.out", "w", stdout);

    int n;
    int m;

    scanf ("%d %d", &n, &m);

    for ( int i = 0; i < m; i++ ) {
        scanf ("%d", & a [i].charge);
        scanf ("%d", & a [i].amount);
    }

    for ( int i = 0; i < m; i++ ) {
        for ( int j = i + 1; j < m; j++ ) {
            if ( a [i].charge > a [j].charge )
                swap (a [i], a [j]);
        }
    }

    int total = 0;
    int index = 0;
    int cost = 0;

    while ( total < n ) {
        if ( a [index].amount + total <= n ) {
            total += a [index].amount;
            cost += (a [index].amount * a [index].charge);
        }

        else {
            cost += ((n - total) * a [index].charge);
            total += (n - total);
        }

        index++;
    }

    printf ("%d\n", cost);

    return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s