#include using namespace std; using ll = long long; #define FOR(i,a,b) for(ll i=(a);i<(b);++i) #define ALL(v) (v).begin(), (v).end() #define p(s) cout<<(s)<> Gx >> Gy >> N >> F; FOR(i, 0, 101){ FOR(j, 0, 101){ M[i][j] = inf; } } // 初期コスト FOR(i, 0, 101){ FOR(j, 0, 101){ M[i][j] = (i+j)*F; } } FOR(i, 0, N){ ll x, y, c; cin >> x >> y >> c; FOR(i, 0, 101){ FOR(j, 0, 101){ ll ny = i + y; ll nx = j + x; if(ny<101 && nx<101){ M[ny][nx] = min(M[ny][nx], M[i][j]+c); } } } } p(M[Gy][Gx]); return 0; }