d[110][110];a,b,c,x,y,n,k,p,q,t;main(i){for(scanf("%d%d%d%d",&x,&y,&n,&k);i--+n;scanf("%d%d%d",&a,&b,&c))for(p=x;p>=a;p--)for(q=y;q>=b;q--)d[p][q]>=(t=d[p-a][q-b]+c)?d[p][q]=i?t:(p+q)*k:0;printf("%d",d[x][y]);}