Maximizing Drink Selection under Constraints

You are given n different types of drinks. Each drink has a cost c_i, an expected demand (which is not used in this problem) and a storage requirement s_i. Amy has a limited budget B and a limited storage capacity C. Your task is to determine the maximum number of different types of drinks Amy can stock without exceeding her budget and storage constraints.

The problem can be modeled as a 2D knapsack problem. You need to select a subset of drinks such that the total cost does not exceed B and the total storage does not exceed C. The objective is to maximize the number of drinks selected.

Note: The expected demand provided for each drink is not used in the decision process.

Constraints:

• 1 ≤ n ≤ 1000
• 0 ≤ B, C ≤ 10⁴
• 1 ≤ c_i, s_i ≤ 10⁴

The mathematical formulation for this problem is:

[ \max ; \text{count} ]

subject to:

[ \sum_{i\in S} c_i \le B, \quad \sum_{i\in S} s_i \le C, ]

where (S) is the set of chosen drinks. Your goal is to maximize (|S|), the number of drinks in (S).

inputFormat

The first line of input contains three integers n, B, and C where:

• n is the number of different types of drinks.
• B is the available budget.
• C is the available storage capacity.

Each of the next n lines contains three integers: c_i (the cost of the drink), an integer representing expected demand (which is not used in the problem), and s_i (the storage requirement for the drink).

outputFormat

Output a single integer, which is the maximum number of different drinks that can be stocked without exceeding the budget B and storage capacity C.

## sample

4 10 12
3 5 4
2 7 2
4 6 3
5 8 5

3