#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_ITM_MAX		3000									// 最大料理数
#define D_TIME_MAX		3000									// 最大時間

// 内部構造体 - 料理情報
typedef struct Itm {
	int miTime;													// 時間
	int miVal;													// 美味しさ
} Itm;

// 内部変数
static FILE *szpFpI;											// 入力
static Itm sz1Itm[D_ITM_MAX];									// 料理
static int siICnt;												// 料理数
static int siTime;												// 時間

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// １行出力
int
fOutLine(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// 最大値 - セット
int
fSetMax(
	int piSNo					// <I> 開始位置
	, int piENo					// <I> 終了位置
	, int *pipVal				// <I> 美味しさ
	, int *pipRet				// <O> 最大値
)
{
	int i, j;

	// 初期値
	memcpy(pipRet, pipVal, sizeof(int) * siTime);

	// 最大値 - 更新
	for (i = piSNo; i <= piENo; i++) {
		for (j = siTime - 1 - sz1Itm[i].miTime; j >= 0; j--) {
			int liTo = j + sz1Itm[i].miTime;
			int liNew = pipRet[j] + sz1Itm[i].miVal;
			if (pipRet[liTo] < liNew) {
				pipRet[liTo] = liNew;
			}
		}
	}

	return 0;
}

// 最大値 - 取得
int
fGetMax(
	int piSNo					// <I> 開始位置
	, int piENo					// <I> 終了位置
	, int *pipVal				// <I> 美味しさ
)
{
	int i;

	// 残り１つ
	if (piSNo == piENo) {
		int liMax = 0;
		for (i = 0; i < siTime; i++) {
			if (liMax < pipVal[i]) {
				liMax = pipVal[i];
			}
		}
		return liMax + sz1Itm[piSNo].miVal;
	}

	// 中間位置
	int liMNo = (piSNo + piENo) / 2;

	// 左側へ
	int li1Val[D_TIME_MAX];
	fSetMax(liMNo + 1, piENo, pipVal, li1Val);
	int liL = fGetMax(piSNo, liMNo, li1Val);

	// 右側へ
	fSetMax(piSNo, liMNo, pipVal, li1Val);
	int liR = fGetMax(liMNo + 1, piENo, li1Val);

	// 最大値 - 取得
	if (liL > liR) {
		return liL;
	}
	else {
		return liR;
	}
}

// 実行メイン
int
fMain(
)
{
	int i;
	char lc1Buf[1024];

	// 料理数・時間 - 取得
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d", &siICnt, &siTime);

	// 料理 - 取得
	for (i = 0; i < siICnt; i++) {
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		sscanf(lc1Buf, "%d%d", &sz1Itm[i].miTime, &sz1Itm[i].miVal);
	}

	// 最大値 - 取得
	int li1Val[D_TIME_MAX];
	memset(li1Val, 0, sizeof(li1Val));
	return fGetMax(0, siICnt - 1, li1Val);
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	liRet = fMain();

	// 出力
	sprintf(lc1Buf, "%d\n", liRet);
	fOutLine(lc1Buf);

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}



Measured memory_bytes: 384