#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define FARA_NUMAR 1005
#define MARE 5894759
#define LANTZ_DA_HAUR_MERITA_SHMEKERU 0
FILE *teancu_da_lei_vechi=fopen("energii.in", "r"), *teancu_da_euroi=fopen("energii.out", "w");
long sum[10011000], i, j, n, k, s;

typedef struct am_valoare_si_bishtari
{
	int e, c;
	float r;
};

am_valoare_si_bishtari v[FARA_NUMAR];

void da_valoare_la_jupan()
{
	long c=0;
	fscanf(teancu_da_lei_vechi, "%ld%ld", &n, &k);
	for (i=1;i<=n;i++)
	{
		fscanf(teancu_da_lei_vechi, "%d%d", &v[i].e, &v[i].c);
		s+=v[i].e;
		c+=v[i].c;
		v[i].r=v[i].e/v[i].c;
	}
	if (s<k)
	{
		fprintf(teancu_da_euroi, "-1");
		exit(LANTZ_DA_HAUR_MERITA_SHMEKERU);
		fclose(teancu_da_lei_vechi);
		fclose(teancu_da_euroi);
	}
	else
		if (s==k)
		{
			fprintf(teancu_da_euroi, "%ld", c);
			exit(LANTZ_DA_HAUR_MERITA_SHMEKERU);
			fclose(teancu_da_lei_vechi);
			fclose(teancu_da_euroi);
		}
	memset(sum, MARE, (1+n)*(n+1));
}

/*void sorteaza_puradeii_dupa_valoare()
{
	long CAPO_DI_TUTTI_CAPPI;
	int INTERLOPU=0
	CAPO_DI_TUTTI_CAPPI=n;
	while(CAPO_DI_TUTTI_CAPPI>1)
	{
		CAPO_DI_TUTTI_CAPPI/=2;
		do{
			INTERLOPU=0;
			for(int PIRANDA=1;PIRANDA<=n-CAPO_DI_TUTTI_CAPPI;PIRANDA++)
				if(sum[PIRANDA]>sum[PIRANDA+CAPO_DI_TUTTI_CAPPI])
				{
					sum[PIRANDA]=sum[PIRANDA]^sum[PIRANDA+CAPO_DI_TUTTI_CAPPI];
					sum[PIRANDA+CAPO_DI_TUTTI_CAPPI]=sum[PIRANDA]^sum[PIRANDA+CAPO_DI_TUTTI_CAPPI];
					sum[PIRANDA]=sum[PIRANDA]^sum[PIRANDA+CAPO_DI_TUTTI_CAPPI];
					INTERLOPU++;
				}
		}while(INTERLOPU!=0);
	}
}*/

void dau_bishtari_la_lautari()
{
	for (i=1;i<=n;i++)
	{
		for (j=k;j>=0;j--)
			if (sum[i]!=MARE&&sum[j+v[i].e]<sum[j]+v[i].c)
				sum[j+v[i].e]=sum[j]+v[i].c;
			if (sum[v[i].e]>v[i].c)
				sum[v[i].e]=v[i].c;
	}
}

void mor_dusmanii_cand_scot_banu()
{
	long cel_mai_shukar_puradel=MARE;
	for (i=k;i<=s;i++)
		if (sum[i]<cel_mai_shukar_puradel)
			cel_mai_shukar_puradel=sum[i];
	fprintf(teancu_da_euroi, "%ld", cel_mai_shukar_puradel);
}

int main()
{
	da_valoare_la_jupan();
//	sorteaza_puradeii_dupa_valoare();
	dau_bishtari_la_lautari();
	mor_dusmanii_cand_scot_banu();
	fclose(teancu_da_lei_vechi);
	fclose(teancu_da_euroi);
	return (LANTZ_DA_HAUR_MERITA_SHMEKERU);
}