from copy import deepcopy Gx, Gy, N, F = map( int, input().split() ) X = [] Y = [] C = [] for i in range( N ): x, y, c = map( int, input().split() ) X.append( x ) Y.append( y ) C.append( c ) INF = int( 1e15 ) dp = [ INF for i in range( Gy + 1 ) ] dp = [ deepcopy( dp ) for i in range( Gx + 1 ) ] dp = [ deepcopy( dp ) for i in range( N + 1 ) ] dp[ 0 ][ 0 ][ 0 ] = 0 for i in range( N ): for j in range( Gx + 1 ): for k in range( Gy + 1 ): if j + X[ i ] <= Gx and k + Y[ i ] <= Gy: dp[ i + 1 ][ j + X[ i ] ][ k + Y[ i ] ] = min( dp[ i + 1 ][ j + X[ i ] ][ k + Y[ i ] ], dp[ i ][ j ][ k ] + C[ i ] ) if j + 1 <= Gx: dp[ i ][ j + 1 ][ k ] = min( dp[ i ][ j + 1 ][ k ], dp[ i ][ j ][ k ] + F ) dp[ i + 1 ][ j + 1 ][ k ] = min( dp[ i + 1 ][ j + 1 ][ k ], dp[ i ][ j ][ k ] + F ) if k + 1 <= Gy: dp[ i ][ j ][ k + 1 ] = min( dp[ i ][ j ][ k + 1 ], dp[ i ][ j ][ k ] + F ) dp[ i + 1 ][ j ][ k + 1 ] = min( dp[ i + 1 ][ j ][ k + 1 ], dp[ i ][ j ][ k ] + F ) print( dp[ N ][ Gx ][ Gy ] )