Space Shuttle Food Optimization

The space shuttle has limited volume and must carry food items with specific volume, mass, and calorie values. Carrying excess weight wastes fuel and money, so it is important to optimize the selection of foods on board.

You are given n food items. Each item has three attributes: volume, mass, and calories. Additionally, you are provided with two constraints: the maximum allowable volume \(V\) and the maximum allowable mass \(M\). Determine the maximum total calories that can be achieved by choosing a subset of the food items such that the total volume does not exceed \(V\) and the total mass does not exceed \(M\). Each food item can be selected at most once.

The problem can be formulated as a 0/1 knapsack problem with two constraints:

\[ \begin{aligned} &\text{Maximize } \sum_{i=1}^{n} c_i x_i,\\ &\text{subject to } \sum_{i=1}^{n} v_i x_i \le V,\\ &\ \ \ \ \sum_{i=1}^{n} m_i x_i \le M,\\ & x_i \in \{0,1\} \quad (1 \le i \le n). \end{aligned} \]

inputFormat

The first line contains three integers \(n\), \(V\), and \(M\) representing the number of food items, the maximum allowable volume, and the maximum allowable mass, respectively.

Each of the following \(n\) lines contains three integers: volume, mass, and calories of each food item.

Example:

3 10 10
5 5 100
6 6 150
4 4 80

outputFormat

Output a single integer representing the maximum total calories that can be achieved without exceeding the given volume and mass constraints.

Example:

180

sample

3 10 10
5 5 100
6 6 150
4 4 80

180