Stepan's Exercises#7238
Stepan is determined to excel not only in competitive programming but also in sports. However, it's been a while since his last workout, so he needs to start from scratch to get back in shape.
Finding suitable exercises proved challenging, so Stepan turned to the Internet for inspiration. He discovered a website offering several training series, each lasting days. For each of these days, there is an "exercise of the day" with recommendations on how many times to perform it, specified as A_i - B_i. This means the exercise should be done between A_i and B_i times to effectively build strength. Doing it fewer than A_i or more than B_i times could be counterproductive. To avoid injury, Stepan will perform the exercise within the recommended range or not at all.
After reviewing the exercises, Stepan realized the course was not beginner-friendly, but he decided to adapt it to his level. He knows that learning the -th exercise will cost him K_i strength levels, but performing it times will increase his strength by F_i \cdot X. Stepan cannot attempt an exercise if his current strength level is below K_i. On days when he lacks the strength or time, he can skip the workout, and his strength level will remain unchanged. Stepan also knows that if he performs an exercise more than times in one day, he will need to rest for the next days.
If Stepan exceeds repetitions on any of the last days of the series, he will begin his rest period the following day, continuing beyond the series' end. Stepan aims to maximize his strength gains over the days. For each training series, help him determine the highest strength level he can achieve by the end. Initially, Stepan's strength level is zero.
The first line contains a single integer (1 \le N \le 10^5) — the number of training days.
The second line contains two integers and (1 \le T \le 10^6, 1 \le D \le 10^5), indicating that if Stepan performs an exercise more than times on any day, he must rest for the next days. The following lines describe the exercises, with the i+2-th line detailing the exercise for day . Each exercise is described by the numbers A_i, B_i, K_i, F_i (0 \le K_i \le 10^9, 1 \le A_i \le B_i \le 10^6, 1 \le F_i \le 10^6), separated by spaces, where A_i, B_i are the recommended minimum and maximum repetitions, K_i is the strength level lost when learning the exercise, and F_i is the strength level gained per repetition.
The first line should contain a single integer — the maximum strength level Stepan can achieve by the end of the training. The second line should list integers X_i — the number of times the exercise was performed on day . If he rested on day , output .
Example 1
To maximize strength, on the first day, the exercise should be performed times to avoid resting the next day. On the second day, Stepan can gain strength levels (losing levels when learning and performing the exercise times), but he will then need to rest on the third day.
On the fourth day, he gains levels, and since he performed the exercise more than times, he must skip the fifth day.