hugo_venhac

//hugo_venha_oanhnhau
#include<iostream>
#define endl '\n'
using namespace std;

int N, ans;
int creeps[7][3];
int price_gate[7];

void copy_arr(int arr1[7][3], int arr2[7][3])
{
	for(int i = 0; i < N; ++i)
		for(int j = 0; j < 3; ++j)
			arr2[i][j] = arr1[i][j];
}

void backtrack(int x, int crs, int score)
{
	if(score >= ans)	return;
	if(x == N)
	{
		if(score < ans)
			ans = min(ans, score);
		return;
	}
	for(int i = 1; i <= 3; ++i)
	{
		if(i == 1)	backtrack(x + 1, crs, score + price_gate[x]);	//Neu qua cong do, nap tien vao cong -> score tang, crs khong doi, x them 1 cong
		if(i == 2)	
		{
			creeps[x][1] = creeps[x][0];	//Nap linh vao quan minh
			backtrack(x + 1, crs + creeps[x][0], score + price_gate[x]*2); //Neu mua linh, score cong them gap 2, linh cong do them, tong crs them linh
			creeps[x][1] = 0;	//Quay lui, creeps cua cong do ve lai 0
		}
		if(i == 3 && crs >= creeps[x][0])
		{
			int copy_crs[7][3];
			copy_arr(creeps, copy_crs);	//copy mang creeps truoc khi backtrack de ty quay lui
			int enemy =  creeps[x][0];	//Dat bien so linh quan dich = linh cong do

			for(int j = 0; j < N; ++j)	//Buoc 1: Cho moi tk quan cong do len 1 lan danh
				if(creeps[j][1] > 0)
					creeps[j][2]++;	//So lan danh cua cong do tang 1 lan

			for(int j = 0; j < N; ++j)	//Buoc 2: Scan linh de danh
			{
				if(creeps[j][1] > 0)	//Neu cong do minh co mua linh
				{
					if(creeps[j][1] > enemy)	//Neu so quan lon hon dich -> linh giam theo so luong dich, dich = 0
					{
						creeps[j][1] -= enemy;
						enemy = 0;
					}
					if(creeps[j][1] <= enemy) //Neu so quan nho hon hoac bang dich -> linh, so lan danh = 0, dich giam theo so luong quan
					{
						enemy -= creeps[j][1];	
						creeps[j][2] = 0;
						creeps[j][1] = 0;
					}
					if(enemy == 0)	break;	//Neu so linh dich da het, break khoi tim quan dong minh nx
				}
			}

			for(int j = 0; j < N; ++j)	//Buoc 3: Kiem tra xem co cong nao danh 3 lan chua, neu danh 3 lan -> cho giai tan
				if(creeps[j][2] == 3)
				{
					creeps[j][2] = 0;
					creeps[j][1] = 0;
				}
			crs = 0;	//reset creeps de cong lai tong quan linh sau tran chien
			for(int j = 0; j < N; ++j)
				if(creeps[j][1] > 0)	//Neu cong do con quan ta -> cong vao crs
					crs += creeps[j][1];

			backtrack(x + 1, crs, score);

			copy_arr(copy_crs, creeps);
			crs = 0;	//Sau backtrack, reset crs, copy lai mang arr cu, cong lai crs va quay lui tiep
			for(int j = 0; j < N; ++j)
				if(creeps[j][1] > 0)	//Neu cong do con quan ta -> cong vao crs
					crs += creeps[j][1];
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	freopen("inp.txt","r",stdin);
	freopen("out.txt","w",stdout);
	cin.tie(0);

	ans = 0;
	cin >> N;
	for(int i = 0; i < N; ++i)
	{
		cin >> creeps[i][0] >> price_gate[i];
		ans += price_gate[i];
	}

	backtrack(0,0,0);

	cout << ans << endl;
	return 0;
}