UVa 12324 - Philip J. Fry Problem

// UVa 12324 - Philip J. Fry Problem

#include <iostream>
#include <string.h>
using namespace std;

#define ttype unsigned long long

int main() {
	int n;
	while (cin >> n && n) {
		ttype t[100];
		int b[100];
		for (int i = 0; i < n; i++)
			cin >> t[i] >> b[i];

		bool halved[100];
		memset(halved, false, sizeof(halved));

		for (int i = n - 1; i >= 0; i--) {
			while (b[i] > 0) {
				int s;
				bool first = true;
				for (int j = i + 1; j < n; j++) {
					if (!halved[j] && (first || t[j] > t[s])) {
						s = j;
						first = false;
					}
				}
				if (first)
					break;
				halved[s] = true;
				b[i]--;
			}
		}
		ttype sol = 0;
		for (int i = 0; i < n; i++)
			if (halved[i])
				sol += (t[i] >> 1);
			else
				sol += t[i];
		cout << sol << endl;
	}
	return 0;
}