Maximize Survival by Minimizing Energy Consumption in Homework Scheduling

Every day, little \(A\) must complete homework totaling at least \(w\) tons. If he fails to reach this target, he will be punished by little \(S\) and die immediately. Initially, little \(A\) has \(x\) units of energy. Every homework task he does consumes energy irreversibly and his energy may never drop below zero.

There are \(n\) types of homework available. Each type has the following attributes:

• \(x_i\): the energy consumed by one copy of this homework type.
• \(w_i\): the weight of one copy (in tons).
• \(t_i\): the deadline. Homework of this type cannot be done after \(t_i\) days from today (i.e. it is available on all days \(d\) such that \(d \le t_i\)).

There is an infinite supply of each homework type. Due to the overwhelming number of assignments, you are asked to design a plan that maximizes the number of days little \(A\) survives (i.e. the number of days he can meet his homework target). When the maximum number of days is achieved, the plan should also maximize his remaining energy.

Note that on each day, little \(A\) can select any number (including multiple copies) of any available homework type. For each day \(d\), let \(S_d\) be the set of homework types with \(t_i \ge d\). You must choose a combination of homework from \(S_d\) whose total weight is at least \(w\) and whose total energy cost is minimized. Let this minimum energy cost be \(f(d)\). Then little \(A\)'s plan is feasible for day \(d\) if his remaining energy is at least \(f(d)\). The objective is to maximize the number of consecutive days starting from day 1 such that little \(A\) can perform homework each day. In case of ties, the plan with the maximum remaining energy after all possible days should be chosen.

If it is impossible to meet the daily requirement on some day because no combination of available homework can achieve at least \(w\) tons, little \(A\) dies that day.

inputFormat

The input consists of multiple lines:

1. The first line contains three integers \(n\), \(x\), and \(w\) separated by spaces, where \(n\) is the number of homework types, \(x\) is the initial energy, and \(w\) is the minimum total weight (in tons) required per day.
2. The next \(n\) lines each contain three integers \(x_i\), \(w_i\), and \(t_i\) separated by spaces, representing the energy cost, weight, and deadline (in days) of the \(i\)-th homework type, respectively.

outputFormat

Output two integers separated by a space: the maximum number of days little \(A\) can survive and his remaining energy after those days.

sample

2 10 5
3 2 3
4 3 2

1 3