How can I solve this classical dynamic programming

问题:

There are N jewellery shop(s). Each jewellery shop has three kinds of coins - Gold, Platinum, and Diamond having worth value A, B, and C respectively. You decided to go to each of N jewellery shop and take coins from each of the shop. But to do so following conditions must satisfy -

You can take at most 1 coin from an individual shop. You can take at most X coins of Gold type. You can take at most Y coins of Platinum type. You can take at most Z coins of Diamond type. You want to collect coins from shops in such a way that worth value of coins collected is maximised.

Input Format :

The first line contains an integer N. Where N is the number of jewellery shops. The second line contains three integers X, Y, Z. Where X, Y, Z denotes the maximum number of coins you can collect of type Gold, Platinum, and diamond respectively. Then N lines contain three space-separated integers A, B, C. Where A, B, C is the worth value of the Gold, Platinum, and diamond coin respectively.

Output Format :

Print a single integer representing the maximum worth value you can get.

Constraints :

1 <= N <= 200

1 <= X , Y , Z <= N

1 <= A , B , C < 10 9

Example : -

4 2 1 1 5 4 5 4 3 2 10 9 7 8 2 9

Answer:-

27(9+9+5+4)

I tried the obvious greedy approach but it failed :-)