#include #include #include #include #include #include /* :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: :::::::::::::::::::::::::::::::::::::::::::::'''```````::::::::::::::::::: ::::::::::::::::::::::::::::::::::::::::''`_,-''.,... `:::::::::::::::::: :::::::::::::::::::::::::::::::::::::' _,-',;;!!!!!!!!!; `:::::::::::::::: ::::::::::::::'`````:::::::::::::'' .-' ; `:::::::::::::: :::::::::' ;!!!!!!!!; ``:::::' ;' ,c$$$$$$$$$$$CC<<" ````_ :::::::::::::: :::::::' ;!!!!!!!!!!!!!; ' ;! z$$$$$$$$$$$$$$$$$$$$$$??". :::::::::::::: ::::::: ` ,c `::::::::::::::::::::::::: MMn.`"?hc,d$$$$$$$$$$$$$$$$$$. `P $P' -??P== `::::::::::::::::::::::: MMMMMnx`"?$$$$$$$$$$$P".,.`"??$ccccc$.z$$$$. `' .:::::::::::::::::' '' MMMMMM,' .?$$$$$$$$$$ d$$$ d$$$$$$$$$$$$$h..``::::::::::::::::' MMMMMMMn `?$$$$$$$$$$,.?$$h. =."?$$$$$$$$$$$$$$hc,.``'::::::::::' MMMMMMMM ;, `"??$$$$$$h ?$$h. -m,``""??$$$$$$$$$$$$$c,.``````' MMMMMMM> !!! ?cc,.,d$$$$h.`"?$hc `P .`"?$$$$$$$$$$$$$$$$$$$ .: MMMMMMM ,!!'. $$$$$$$$$??=== `"""=c, " P n. "$$$$$$$$$$$$$$$$c_ ,.:::: MMMMMMP !!! Mr<$$$$"".,c,;M ;'$$$$$$$$$>4M `!!! 4MMbn.`"=cc," -'P",c=.,.`.. .= ::::::::: MMMMM' !!! dMb $$$$$$$$P MM> !!! 4MMMMMMr :..`"-._""Pr4"'-P" .,.`::::::::: MMMM' ;!!! 4MMMMMMb :::::.. "-=cczyycc??" .::::::::: MMMP ;!!! 4MMMMMMMr`:::::::::.........::::::::::::: MMP';!!! ;MMMMMMn,.".uMMMMM ;!!! MMMMMMMMM,`:::::::::::::::::::::::::::::: MM ;!!!! MMMMMMMMMMMMMMMMMM !!!! MMMMMMMMMb `::::::::::::::::::::::::::::: M" !!!! uMMMMMMMMMMMMMMMMMP !!! ;MMMMMMMMMMx ::::::::::::::::::::::::::::: P.!!!! ,MMMMMMMMMMMMMMMMMM ,!!! MMMMMMMMMMMMx`:::::::::::::::::::::::::::: !!!!> MMMMMMMMMMMMMMMMMMP !!!',MMMMMMMMMMMMM `::::::::::::::::::::::::::: */ int main() { int gx, gy, crystals, fee; std::cin >> gx >> gy >> crystals >> fee; std::vector, int> > v(crystals); for (int i = 0; i < crystals; i++) { int x, y, f; std::cin >> x >> y >> f; v[i] = { {x, y}, f }; }; long long dp[100][100][100]; for (int i = 0; i < 100; i++) { for (int j = 0; j < 100; j++) { for (int k = 0; k < 100; k++) { dp[i][j][k] = 10000000000; } } } for (int i = 0; i < 100; i++) { dp[0][0][i] = 0; } for (int i = 0; i <= gy; i++) { for (int j = 0; j <= gx; j++) { dp[i + 1][j][0] = std::min(dp[i + 1][j][0], dp[i][j][0] + fee); dp[i][j + 1][0] = std::min(dp[i][j + 1][0], dp[i][j][0] + fee); for (int k = 0; k < crystals; k++) { dp[i][j][k + 1] = std::min(dp[i][j][k + 1], dp[i][j][k]); if (v[k].first.first + j <= gx && v[k].first.second + i <= gy) { dp[i + v[k].first.second][j + v[k].first.first][k + 1] = std::min(dp[i + v[k].first.second][j + v[k].first.first][k + 1], dp[i][j][k] + v[k].second); } } } } long long ans = dp[gy][gx][0]; for (int i = 0; i < crystals; i++) { ans = std::min(ans, dp[gy][gx][i + 1]); } std::cout << ans << std::endl; return 0; }