// 我真誠地保證：
// 我自己獨立地完成了整個程序從分析、設計到編碼的所有工作。
// 如果在上述過程中，我遇到了什么困難而求教于人，那么，我將在程序實習報告中
// 詳細地列舉我所遇到的問題，以及別人給我的提示。
// 我的程序里中凡是引用到其他程序或文檔之處，
// 例如教材、課堂筆記、網上的源代碼以及其他參考書上的代碼段,
// 我都已經在程序的注釋里很清楚地注明了引用的出處。
// 我從未沒抄襲過別人的程序，也沒有盜用別人的程序，
// 不管是修改式的抄襲還是原封不動的抄襲。
// 我編寫這個程序，從來沒有想過要去破壞或妨礙其他計算機系統的正常運轉。
// 學生：朱詩雄

/*
	文件名稱：	bag
	項目名稱：	背包問題
	創建者：	朱詩雄

	輸入格式：第一行輸入背包數目n，接下來每一行輸入這n個背包的重量和價值，最后一行輸入總重量t。
	例：
	2
	5 56
	3 56
	4
	輸出：
	the best answer is:3
	the max value is:56
*/
#include<iostream>
using namespace std;

int main()
{
	int n;					//背包數量
	cin>>n;
	int *w,*v;
	w=new int [n];
	v=new int [n];
	for(int i=0;i<n;i++)
		cin>>w[i]>>v[i];			//輸入背包重量和價值
	int t;					//總重量T		
	cin>>t;	
	int num=1;
	for(i=0;i<n;i++)		//num用來算2的n次方
		num*=2;
	int k,l,value,weight,vmax=0;
//value是總價值，weight是總重量,vmax是滿足題意的最大總價值,j是滿足題意的最優方案
	for(int j=0;j<num;j++)
	{
		value=0;weight=0;k=j;
		for(int i=0;i<n;i++)
		{
			weight=weight+(k%2)*w[i];
			value=value+(k%2)*v[i];
			k=k/2;
		}
		if( (weight<=t) && (value>vmax) )	//總重量小于t，總價值大于vmax，這方案是比前面更好的方案
		{
			vmax=value;l=j;
		}
	}
	cout<<"the best answer is";
	for(i=0;i<n;i++,l=l/2)
		if(l%2==1) cout<<w[i]<<' ';		//輸出最優方案
	cout<<endl;
	cout<<"the max value is:"<<vmax<<endl;		//輸出滿足題意的最大總價值
	return 0;
}