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

// 内部定数
#define D_ITM_MAX		40												// 最大薬品数
#define D_WEIGHT_MAX	10												// 最大含有量
#define D_WEIGHT_RNG	(D_ITM_MAX * D_WEIGHT_MAX)						// 含有量の範囲

// 内部構造体 - 物質情報
typedef struct Itm {
	int miA;															// Aの含有量
	int miB;															// Bの含有量
	int miVal;															// 価格
} Itm;

// 内部変数
static Itm sz1Itm[D_ITM_MAX];											// 薬品
static int siICnt;														// 薬品数
static int siMinA;														// 最低量 - A
static int siMinB;														// 最低量 - B
static int si3Val[D_ITM_MAX + 5][D_WEIGHT_RNG + 5][D_WEIGHT_RNG + 5];	// 価格表[薬品位置][Aの含有量][Bの含有量]

// 内部変数 - テスト用
#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 ldVal1 = (lzpVal1->miA + lzpVal1->miB) / lzpVal1->miVal;
	double ldVal2 = (lzpVal2->miA + lzpVal2->miB) / lzpVal2->miVal;

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

	return 0;
}

// 価格表セット
int
fSetVal(
	int piINo					// <I> 薬品 0～
	, int piA					// <I> Aの含有量
	, int piB					// <I> Bの含有量
	, int piVal					// <I> 価格
)
{
	// 価格表
	if (si3Val[piINo][piA][piB] > 0) {
		if (si3Val[piINo][piA][piB] <= piVal) {
			return 0;
		}
	}
	si3Val[piINo][piA][piB] = piVal;

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

	// 対象データ
	Itm *lzpItm = &sz1Itm[piINo];

	// 薬品の選択有無
	fSetVal(piINo + 1, piA + lzpItm->miA, piB + lzpItm->miB, piVal + lzpItm->miVal);	// あり
	fSetVal(piINo + 1, piA, piB, piVal);												// なし

	return 0;
}

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

	// データ初期化
	memset(si3Val, 0, sizeof(si3Val));							// 価格表

	// テストファイルオープン
#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

	// 薬品数・最低数(A,B)取得
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpT);
#else
	fgets(lc1Buf, sizeof(lc1Buf), stdin);
#endif
	sscanf(lc1Buf, "%d%d%d", &siICnt, &siMinA, &siMinB);

	// 薬品取得
	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%d", &sz1Itm[i].miA, &sz1Itm[i].miB, &sz1Itm[i].miVal);
	}

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

	// 価格表セット
	fSetVal(0, 0, 0, 0);

	// 最低価格の検索
	int liMin = INT_MAX;
	for (i = 1; i <= siICnt; i++) {
		int liA = siMinA;
		int liB = siMinB;
		while (1) {

			// 含有量の範囲チェック
			if (liA > D_WEIGHT_RNG) {
				break;
			}
			if (liB > D_WEIGHT_RNG) {
				break;
			}

			// 価格表のチェック
			if (si3Val[i][liA][liB] > 0) {
				if (liMin > si3Val[i][liA][liB]) {
					liMin = si3Val[i][liA][liB];
				}
			}

			// 次の含有量
			liA += siMinA;
			liB += siMinB;
		}
	}

	// 結果セット
	if (liMin == INT_MAX) {
		sprintf(lc1Out, "-1\n");
	}
	else {
		sprintf(lc1Out, "%d\n", liMin);
	}

	// 結果表示
#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: 29056