401442: GYM100451 K TopoCM++

Polycarp is taking part in a programming contest based on new and innovative rules called TopoCM++. There are n problems in the contest and the contest has unlimited duration. According to the rules, each problem has expected submission time, the expected submission time of the i-th problem is t_i.

Ideally, a contestant should solve each problem not later than in time t_i, but in the real world some contestants solve problems later. As the contest lasts infinitely, each contestant will solve all the problems sooner or later. The score of the contestant depends on the maximum delay among all the problems. Thus the goal of each contestant is to solve all the problems in time. If it is impossible, the goal is to minimize the maximum value of r_i - t_i, where r_i is the time when the i-th problem was solved.

Polycarp has made detailed analysis and found out that for the i-th problem he needs a_i time units to come up with an algorithm and b_i time units to code it. So in total, he solves the i-th problem in a_i + b_i time units.

Polycarp is not a multitasking operating system, so he can't do several things at the same time. Polycarp is planning to organize his work in the following way. In total, he has 2n jobs: n jobs to come up with an algorithm (thinking jobs) and n jobs to write a code (coding jobs). He will do the jobs in any order with the only constraint: for each problem he should first come up with an algorithm (think) and only after it he can write a code (code) for the problem. He can't interrupt jobs. Once he has started the job, he should finish it before switching to any other one.

Each time Polycarp switches between a type of activity (from thinking to code or back) he spends some time to be ready for new activity. Polycarp knows two values f_t and f_c, where f_c is the time he needs to prepare for thinking and f_c is the time he needs to prepare for coding. He needs f_t time units to prepare before the first job (for sure, it is a thinking job) and each time he changes the type of jobs, he needs f_c or f_t time units.

Help Polycarp to find the order of jobs to solve all the problems in time or (if it is impossible) to minimize the delay.

The first line of the input contains three integers n, f_t and f_c (1 ≤ n, f_t, f_c ≤ 2·10⁵). The following n lines contain the descriptions of the problems, one description per line. The i-th line contains a_i, b_i and t_i (1 ≤ a_i, b_i ≤ 2·10⁵; 1 ≤ t_i ≤ 10¹²), where a_i is the time to think for the i-th problem, b_i is the time to code the i-th problem and t_i is the maximum time time to solve it in time.

Print the required minumum delay to solve all the problems. Formally, it is the minimum value for the max{r_i - t_i}, among all problems solved not in time, where r_i is the time when Polycarp solved the i-th problem.

Print the sequence of 2n numbers in the second line. For each i between 1 and n it should contain exactly once  - i and i, where  - i stands for the job to come up with an algorithm for the i-th problem and i stands for the coding job for the i-th problem.

5 2 2
3 3 4
2 1 21
1 3 8
1 3 20
1 2 16

8
-4 -3 -1 1 3 -2 -5 5 2 4