hugovenhasol

#include <iostream>

using namespace std;

int n;

struct door{
	int solinh;
	int chiphi;
};

door doors[100];
int quan[100];
int x[100];
int minans;


int findpos(int index)
{
	int counttd = 0;
	int tmpres = index;
	for (int i = index - 1; i >= 1;  i--)
	{
		if (x[i] == 2) counttd += 1;
		if (counttd == 3) break;
		tmpres = i;
	}
	return tmpres;
}

int checkk(int pos, int index, int solinh)
{
	int countt = 0;
	for (int i = pos; i <= index -1; i++)
		countt += quan[i];
	if (countt >= solinh) return 1;
	return 0;
}

void update(int pos, int solinh)
{
	while (solinh > 0)
	{
		if (solinh > quan[pos])
		{
			solinh -= quan[pos];
			quan[pos] = 0;
		} else
		{
			quan[pos] -= solinh;
			solinh = 0;
		}
		pos++;
	}
}

void update1(int index, int solinh)
{
	index--;
	while (solinh > 0)
	{
		if (x[index] == 1)
		{
			int tmp = doors[index].solinh - quan[index];
			if (solinh < tmp)
			{
				quan[index] += solinh;
				solinh = 0;
			} else
			{
				solinh -= tmp;
				quan[index] = doors[index].solinh;
			}
		}
		index--;
	}
}

void back(int index, int cost)
{
	if (index == n + 1)
	{
		if (cost < minans) minans = cost;
		return;
	}

	if (cost >= minans) return;


	x[index] = 0;
	back(index + 1, cost + doors[index].chiphi);
			
	x[index] = 1;
	quan[index] = doors[index].solinh;
	back(index + 1, cost + 2*doors[index].chiphi);
	quan[index] = 0;
			
	int pos =  findpos(index);
	if (checkk(pos, index, doors[index].solinh))
	{
		x[index] = 2;	//danh
		update(pos, doors[index].solinh); // xoa so quan chet
		back(index + 1, cost);
		update1(index, doors[index].solinh); // restore lai so quan chet
	}
}

int main()
{
	int ntc;
	cin >> ntc;
	for (int tc=1; tc<=ntc; tc++)
	{
		cin >> n;
		for (int i = 1; i <= n; i++)
			cin >> doors[i].solinh >> doors[i].chiphi;
	
		minans = 999999;
		back(1,0);
		cout <<"#"<<tc << " "<< minans << endl;
	}

	
	return 0;
}