#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <ctype.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define REP(x, n) for(int x=0; x < (n); ++x)
#define VAR(v,i) __typeof(i) v=(i)
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i)
#define SIZE(n) (int)n.size()
#define ALL(c) c.begin(),c.end()
#define PB(n) push_back(n)
typedef long long LL;
typedef pair < int , int > PII;
typedef vector < int > VI;
typedef vector < vector < int > > VVI;
typedef vector < bool > VB;
#define MP make_pair
#define ST first
#define ND second
const int INF = 1000000001;
//~~~~~~~~~~~~~~BigNum~~~~~~~~~~~~~~~~~~~~~//
struct BigNum
{
#define REDUCE() while(len>1 && !cyf[len-1]) len--;
		static const int BASE = 1000000000, BD = 9;
		int len, al;
		LL *cyf;
		BigNum ( int v = 0, int l = 2 ) :
			len ( 1 ), al ( l ), cyf ( new LL[l] )
		{
			REP(x, al)
				cyf[x] = 0;
			if ( (cyf[0] = v) >= BASE ) przen ( 1 );
		}
		BigNum ( const BigNum & a ) :
			len ( a.len ), al ( len ), cyf ( new LL[al] )
		{
			REP(x, al)
				cyf[x] = a.cyf[x];
		}
		~BigNum ()
		{
			delete cyf;
		}
		void
		Res ( int l )
		{
			if ( l > al )
			{
				LL *n = new LL[l = max ( l, 2 * al )];
				REP(x, l)
					n[x] = x >= al ? 0 : cyf[x];
				delete cyf;
				cyf = n;
				al = l;
			}
		}

		void
		przen ( int p )
		{
			int x = 0;
			for ( ; x < p || cyf[x] < 0 || cyf[x] >= BASE; x++ )
			{
				Res ( x + 2 );
				if ( cyf[x] < 0 )
				{
					LL i = (- cyf[x] - 1) / BASE + 1;
					cyf[x] += i * BASE;
					cyf[x + 1] -= i;
				}
				else

				if ( cyf[x] >= BASE )
				{
					LL i = cyf[x] / BASE;
					cyf[x] -= i * BASE;
					cyf[x + 1] += i;
				}
			}
			len = max ( len, x + 1 );
			while ( len > 1 && ! cyf[len - 1] )
				len--;
		}
#define OPER1(op) bool operator op (const BigNum &a) const
		OPER1(<)
		{
			if ( len != a.len ) return len < a.len;
			int x = len - 1;
			while ( x && a.cyf[x] == cyf[x] )
				x--;
			return cyf[x] < a.cyf[x];
		}
		OPER1(<=)
		{
			return ! (a < * this);
		}
		BigNum &
		operator= ( int a )
		{
			REP(x, len)
				cyf[x] = 0;
			len = 1;
			if ( cyf[0] = a >= BASE ) przen ( 1 );
			return * this;
		}
#define OPER2(op) BigNum& operator op (const BigNum &a)
		OPER2(=)
		{
			Res ( a.len );
			FORD(x, len - 1, a.len)
				cyf[x] = 0;
			REP(x, a.len)
				cyf[x] = a.cyf[x];
			len = a.len;
			return * this;
		}
		void
		write () const
		{
			printf ( "%d", int(cyf[len - 1]) );
			FORD(x, len - 2, 0)
				printf ( "%0*d", BD, int(cyf[x]) );
		}
		BigNum &
		operator= ( string a )
		{
			int s = a.length ();
			* this = 0;
			Res ( len = s / BD + 1 );
			REP(x, s)
				cyf[(s - x - 1) / BD] = 10 * cyf[(s - x - 1) / BD] + a[x]
						- '0';
			REDUCE();
			return * this;
		}
		void
		operator+= ( int a )
		{
			cyf[0] += a;
			przen ( 1 );
		}
		OPER2(+=)
		{
			Res ( a.len );
			REP(x, a.len)
				cyf[x] += a.cyf[x];
			przen ( a.len );
			return * this;
		}
		OPER1(==)
		{
			if ( a.len != len ) return 0;
			REP(x, len)
				if ( cyf[x] != a.cyf[x] ) return 0;
			return 1;
		}
};
//~~~~~~~~~~~~~~Ford-Bellman~~~~~~~~~~~~~~~~~~~~~//
int V, E, s, t;
struct str
{
		int trg, w;
};
vector < str > G[501];
int d[501];
bool
ford_bellman ( int start )
{
	FOR(i,1,V)
		d[i] = INF;
	d[start] = 0;
	bool change;
	int x;
	for ( x = 1; x <= V; ++x )
	{
		change = true;
		FOR(u,1,V)
			FOREACH(it,G[u])
			{
				int v = it->trg, cost = it->w;
				if ( d[v] > d[u] + cost )
				{
					d[v] = d[u] + cost;
					change = false;
				}
			}
		if ( change ) return true;
	}
	if ( x >= V ) return false;
	return true;
}
//~~~~~~~~~~~~~~Dijkstra~~~~~~~~~~~~~~~~~~~~~//
int V, E, d[50002];
bool ok[50002];
struct str
{
		int trg, w;
		str ( int a, int b )
		{
			trg = a;
			w = b;
		}
};
vector < str > G[50002];
bool
operator < ( str a, str b )
{
	if ( a.w > b.w )
		return true;
	else
		return false;
}
priority_queue < str > Q;

void
dijkstra ( int s )
{
	str tmp ( s, 0 );
	FOR(i,1,V)
	{
		d[i] = INF;
		ok[i] = false;
	}
	d[s] = 0;
	Q.push ( tmp );
	while ( ! Q.empty () )
	{
		str top = Q.top ();
		Q.pop ();
		if ( ! ok[top.trg] )
		{
			ok[top.trg] = true;
			for ( unsigned int i = 0; i < G[top.trg].size (); ++i )
			{
				str akt = G[top.trg][i];
				if ( d[akt.trg] > d[top.trg] + akt.w )
				{
					d[akt.trg] = d[top.trg] + akt.w;
					str tmp ( akt.trg, d[akt.trg] );
					Q.push ( tmp );
				}
			}
		}
	}
}
//~~~~~~~~~~~~~~Floyd-Warchall~~~~~~~~~~~~~~~~~~~~~//
void
floyd_warschall ()
{
	FOR(k,1,V)
	FOR(i,1,V)
		FOR(j,1,V)
				d[i][j] = min ( d[i][j], d[i][k] + d[k][j] );
}
//~~~~~~~~~~~~~~Find-Union - Kruskal~~~~~~~~~~~~~~~~~~~~~//
int V, E, parent[10010], rank[10010];
struct vertex
{
		int from, to, w;
};
bool
operator< ( vertex a, vertex b )
{
	if ( a.w < b.w )
		return true;
	else
		return false;
}
vertex Edges[1000010];
int
Find ( int x )
{
	if ( parent[x] == x ) return x;
	parent[x] = Find ( parent[x] );
	return parent[x];
}
void
Union ( int x, int y )
{
	int u = Find ( x );
	int v = Find ( y );
	if ( rank[u] == rank[v] ) rank[u]++;
	if ( rank[u] > rank[v] )
		parent[v] = u;
	else
		parent[u] = v;
}
long long
kruskal ()
{
	long long cost = 0;
	for ( int i = 1; i <= V; ++i )
	{
		parent[i] = i;
		rank[i] = 0;
	}
	sort ( Edges, Edges + E );
	for ( int i = 0; i < E; ++i )
	{
		int u = Edges[i].from, v = Edges[i].to;
		if ( Find ( u ) != Find ( v ) )
		{
			Union ( u, v );
			cost += Edges[i].w;
		}
	}
	return cost;
}
//~~~~~~~~~~~~~~BFS~~~~~~~~~~~~~~~~~~~~~//
int V, E, n;
vector < int > G[500001];
int d[500001];
void
BFS ( int v )
{
	d[v] = 0;
	queue < int > q;
	q.push ( v );
	while ( ! q.empty () )
	{
		int u = q.front ();
		q.pop ();
		FOREACH(it,G[u])
		{
			if ( d[* it] == - 1 )
			{
				d[* it] = d[u] + 1;
				q.push ( * it );
			}
		}
	}
}

//~~~~~~~~~~~~~~DFS~~~~~~~~~~~~~~~~~~~~~//
#define bialy 0
#define szary 1
#define czarny 2
int V, E, n;
vector < int > G[500001];
stack < int > a;
bool cykl;
char odw[500001] =
{ bialy };
void
DFS ( int v )
{
	odw[v] = szary;
	FOREACH(it,G[v])
	{
		if ( odw[* it] == bialy ) DFS ( G[v][i] );
		if ( odw[* it] == szary ) cykl = true;
	}
	odw[v] = czarny;
	a.push ( v );
}
//~~~~~~~~~~~~~~Longest Common Subsequence~~~~~~~~~~~~~~~~~~~~~//
int
LCS ()
{
	short int m[3001][3001];
	char s[3001][3001], x[3001];
	string a, b;
	cin >> a >> b;
	int dl_a = a.size (), dl_b = b.size ();
	for ( int i = 0; i <= max ( dl_a, dl_b ); ++i )
	{
		m[0][i] = 0;
		m[i][0] = 0;
	}
	for ( int i = 1; i <= dl_a; ++i )
	{
		for ( int j = 1; j <= dl_b; ++j )
		{
			if ( a[i - 1] == b[j - 1] )
			{
				m[i][j] = m[i - 1][j - 1] + 1;
				s[i][j] = '0';
			}
			else
			{
				if ( m[i - 1][j] > m[i][j - 1] )
				{
					m[i][j] = m[i - 1][j];
					s[i][j] = '1';
				}
				else
				{
					m[i][j] = m[i][j - 1];
					s[i][j] = '2';
				}
			}
		}
	}
	int c = 0, i = dl_a, j = dl_b;
	while ( i > 0 && j > 0 )
	{
		if ( s[i][j] == '0' )
		{
			x[c++] = a[i - 1];
			i--;
			j--;
		}
		else if ( s[i][j] == '2' )
			j--;
		else
			i--;
	}
	return m[dl_a][dl_b];
}
//~~~~~~~~~~~~~~problem plecakowy~~~~~~~~~~~~~~~~~~~~~//
int
backpack ()
{
	int v[1001] =
	{ 0 }, s[1001] =
	{ 0 }, p[1001][10001] =
	{
	{ 0 } };
	int n, b;
	scanf ( "%d %d", & n, & b );
	REP(i,n)
		scanf ( "%d %d", & s[i], & v[i] );
	FOR(i,1,n)
	{
		FOR(c,1,b)
		{
			if ( c - s[k] < 0 )
			{
				p[k][c] = p[k - 1][c];
				continue;
			}
			p[k][c] = max ( p[k - 1][c], v[k] + p[k - 1][c - s[k]] );
		}
	}
	return p[n][b];
}

int
main ( int argc, char **argv )
{
	return 0;
}