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

// 内部定数
#define D_ITM_MAX		100													// 最大品物数
#define D_DF_W			3													// 最大の品物の重さの差

// 内部構造体 - 品物情報
typedef struct Itm {
	int miWeight;															// 重さ
	int miVal;																// 価値
} Itm;

// 内部変数
static Itm sz1Itm[D_ITM_MAX];												// 品物
static int siICnt;															// 品物数
static int siSWMax;															// 最大合計重さ
static int siIWMin;															// 最小品物重さ
static int siSVMax;															// 最大合計価値
static int si3Memo[D_ITM_MAX + 5][D_ITM_MAX + 5][D_DF_W * D_ITM_MAX];		// メモ変数[品物][個数][合計重さ] = 価値

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

// ソート関数 - コスパ降順
int
fSortFnc(
	const void *pzpVal1			// <I> 値１
	, const void *pzpVal2		// <I> 値２
)
{
	Itm *lzpVal1 = (Itm *)pzpVal1;
	Itm *lzpVal2 = (Itm *)pzpVal2;

	// コスパ
	double ldV1 = (double)lzpVal1->miVal / (double)lzpVal1->miWeight;
	double ldV2 = (double)lzpVal2->miVal / (double)lzpVal2->miWeight;

	// コスパ降順
	if (ldV1 > ldV2) {
		return(-1);
	}
	else if (ldV1 < ldV2) {
		return(1);
	}

	return 0;
}

// 最大合計価値の更新
int
fUpSVMax(
	int piINo					// <I> 対象品物 0～
	, int piICnt				// <I> 品物数
	, int piWSum				// <I> 合計重さ
	, int piVSum				// <I> 合計価値
)
{
	// 合計重さチェック
	if (piWSum + siIWMin * piICnt > siSWMax) {
		return 0;
	}

	// メモ変数チェック
	if (si3Memo[piINo][piICnt][piWSum] > 0) {
		if (si3Memo[piINo][piICnt][piWSum] >= piVSum) {
			return 0;
		}
	}
	si3Memo[piINo][piICnt][piWSum] = piVSum;

	// 最大合計価値の更新
	if (siSVMax < piVSum) {
		siSVMax = piVSum;
	}

	// 終了チェック
	if (piINo >= siICnt) {
		return 0;
	}

	// 品物の選択有無
	fUpSVMax(piINo + 1, piICnt + 1, piWSum + sz1Itm[piINo].miWeight, piVSum + sz1Itm[piINo].miVal);		// 選択あり
	fUpSVMax(piINo + 1, piICnt, piWSum, piVSum);														// 選択なし

	return 0;
}

// 実行メイン
int
fMain(
	int piTNo					// <I> テスト番号 1～
)
{
	int i;
	char lc1Buf[1024], lc1Out[1024];

	// データ初期化
	siSVMax = 0;												// 最大合計価値
	memset(si3Memo, 0, sizeof(si3Memo));						// メモ変数

	// テストファイルオープン
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo);
	szpFpT = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", piTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#endif

	// 品物数・最大合計重さ取得
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpT);
#else
	fgets(lc1Buf, sizeof(lc1Buf), stdin);
#endif
	sscanf(lc1Buf, "%d %d", &siICnt, &siSWMax);

	// 品物取得
	for (i = 0; i < siICnt; i++) {
#ifdef D_TEST
		fgets(lc1Buf, sizeof(lc1Buf), szpFpT);
#else
		fgets(lc1Buf, sizeof(lc1Buf), stdin);
#endif
		sscanf(lc1Buf, "%d %d", &sz1Itm[i].miWeight, &sz1Itm[i].miVal);
	}

	// 最小品物重さ
	siIWMin = sz1Itm[0].miWeight;

	// ソート
	qsort(sz1Itm, siICnt, sizeof(Itm), fSortFnc);

	// 最小品物重さを減算
	for (i = 0; i < siICnt; i++) {
		sz1Itm[i].miWeight -= siIWMin;
	}

	// 最大合計価値の更新
	fUpSVMax(0, 0, 0, 0);

	// 結果セット
	sprintf(lc1Out, "%d\n", siSVMax);

	// 結果表示
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, lc1Out)) {
		siRes = -1;
	}
#else
	printf("%s", lc1Out);
#endif

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

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

	return 0;
}

int
main()
{

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

	return 0;
}



Measured memory_bytes: 13312