#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) FOR(i,0,n)
#define repr(i,n) for(int i=(n)-1;0<=i;--i)
#define each(e,v) for(auto&& e:(v))
#define all(v) begin(v),end(v)
#define DUMP(x) cerr<<#x<<": "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<": "<<(x)<<" (L"<<__LINE__<<")"<<endl
using namespace std;
using vint = vector<int>;
using vdouble = vector<double>;
using vstring = vector<string>;
using ll = long long;
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

constexpr int INF = 1e9;

int main() {
    int gx, gy, n, f; cin >> gx >> gy >> n >> f;
    int dp[101][101];
    rep(y, gy+1) rep(x, gx+1) dp[x][y] = (x + y) * f;
    rep(i, n) {
        int cx, cy, cc; cin >> cx >> cy >> cc;
        repr(y, gy+1) {
            repr(x, gx+1) {
                if(x < cx || y < cy) continue;
                chmin(dp[x][y], dp[x - cx][y - cy] + cc);
            }
        }
    }
    cout << dp[gx][gy] << endl;
    return 0;
}