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

// 内部定数
#define D_SIZE_MAX		105										// 最大サイズ
#define D_CRS_MAX		55										// 最大クリスタル数

// 内部構造体 - クリスタル情報
typedef struct Crs {
	int miX, miY;												// 移動距離
	int miVal;													// 値段
	double mdCost;												// コスパ
} Crs;

// 内部変数
static FILE *szpFpI;											// 入力
static int siGx, siGy;											// 目的地
static Crs sz1Crs[D_CRS_MAX];									// クリスタル
static int siCCnt;												// クリスタル数
static int siCost;												// 通行料
static int si3Sum[D_CRS_MAX][D_SIZE_MAX][D_SIZE_MAX];			// コスト合計[クリスタル][位置X][位置Y]
static int siMin;												// 最小コスト

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

// 出力
int
fOut(
	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
fSortFnc(
	const void *pzpVal1			// <I> 値１
	, const void *pzpVal2		// <I> 値２
)
{
	Crs *lzpVal1 = (Crs *)pzpVal1;
	Crs *lzpVal2 = (Crs *)pzpVal2;

	// コスパ降順
	if (lzpVal1->mdCost > lzpVal2->mdCost) {
		return -1;
	}
	else if (lzpVal1->mdCost < lzpVal2->mdCost) {
		return 1;
	}

	return 0;
}

// コスト合計 - セット
int
fSetSum(
	int piCNo					// <I> クリスタル 0～
	, int piX					// <I> 位置X
	, int piY					// <I> 位置Y
	, int piSum					// <I> コスト合計
)
{
	// 範囲チェック
	if (piX > siGx) {
		return 0;
	}
	if (piY > siGy) {
		return 0;
	}

	// コスト合計
	if (si3Sum[piCNo][piX][piY] > 0) {
		if (si3Sum[piCNo][piX][piY] <= piSum) {
			return 0;
		}
	}
	si3Sum[piCNo][piX][piY] = piSum;

	// 最小コスト
	if (siMin > piSum) {
		siMin = piSum;
	}

	// 選択中
	if (piCNo < siCCnt) {

		// 選択
		int liSum = piSum - (sz1Crs[piCNo].miX + sz1Crs[piCNo].miY) * siCost + sz1Crs[piCNo].miVal;
		fSetSum(piCNo + 1, piX + sz1Crs[piCNo].miX, piY + sz1Crs[piCNo].miY, liSum);

		// 選択なし
		fSetSum(piCNo + 1, piX, piY, piSum);
	}

	return 0;
}

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

	// 目的地・クリスタル数・通行料 - 取得
	int liCCnt;
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d%d%d", &siGx, &siGy, &liCCnt, &siCost);

	// クリスタル - 取得
	for (i = 0; i < liCCnt; i++) {
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		sscanf(lc1Buf, "%d%d%d", &sz1Crs[siCCnt].miX, &sz1Crs[siCCnt].miY, &sz1Crs[siCCnt].miVal);

		// コスパ
		sz1Crs[siCCnt].mdCost = (double)sz1Crs[siCCnt].miVal / (double)(sz1Crs[siCCnt].miX + sz1Crs[siCCnt].miY);
		if (sz1Crs[siCCnt].mdCost < (double)siCost) {
			siCCnt++;
		}
	}

	// クリスタル - ソート
	qsort(sz1Crs, siCCnt, sizeof(Crs), fSortFnc);

	// コスト合計 - セット
	int liSum = (siGx + siGy) * siCost;
	fSetSum(0, 0, 0, liSum);

	return 0;
}

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

	// データ - 初期化
	siCCnt = 0;													// クリスタル数
	memset(si3Sum, 0, sizeof(si3Sum));							// コスト合計
	siMin = INT_MAX;											// 最小コスト

	// 入力 - セット
#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", siMin);

	// 結果 - 出力
	fOut(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;
}