DMOPC '14 Exam Time P5 - Happy Teachers - Olympiads Online Judge

DMOPC '14 Exam Time P5 - Happy Teachers

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Problem type

Since you managed to cancel all of the exams, the teachers no longer have to spend the day before Exam Review marking them! However, they are still forced to come to school as their employment contract assumes they have exams to mark. This means that the teachers must be in the school for the entire day and since there are no students in class, they must stay at their desks in their respective department office.

Inspired by other schools where teachers dance to "Happy" by Pharrell Williams, you along with other friends decide to go to some teachers and record them happily dancing to the song.

Fortunately, this will prove to be an easy task, as the teachers are already happy due to the cancellation of exams. Since you want the video to make it seem that the teachers at your school are happier than those at other schools, you decide to maximize the total happiness of the video.

To achieve this, you assign a happiness value, $H_i$ ~H_i~ to each teacher. For every second the $i^{th}$ ~i^{th}~ teacher is in the video, the total happiness, $H_t$ ~H_t~, increases by $H_i$ ~H_i~.

However, relying only on happiness values means that one teacher would appear for most of the video, which is not very realistic. Rather than setting a time limit for each teacher, you notice that some teachers have more energy than others. By this, we mean that some teachers might dance for ten seconds while others may simply smile for one second, even if they both have the same happiness level.

To model this, an energy consumption value, $E_i$ ~E_i~, is assigned to each teacher. For every second the $i^{th}$ ~i^{th}~ teacher is in the video he or she loses $E_i$ ~E_i~ of their happiness, with a lower happiness bound of $0$ ~0~. This in turn makes the total happiness lower than it could be and means that it might be time to visit the next teacher.

Unfortunately, you find out that there is a staff meeting in the afternoon where the Principal will ask the teachers why the exams were cancelled thereby reducing the happiness of every teacher to zero. This means that you have a limited time to record the video. Knowing that some teachers are more spontaneous than others, you assign a preparation time, $P_i$ ~P_i~ which is the time it takes for them to prepare for every second they appear plus that one second. That is, if $P_i$ ~P_i~ of the $i^{th}$ ~i^{th}~ teacher is 3, then they will spend 2 seconds preparing for every second they are in the video.

In the case that there are multiple optimum solutions, choose the one that will yield a video with the shortest duration — for more happiness per second.

Input Specification

The next line will consist of $n$ ~n~, the number of teachers in the school.

The next $n$ ~n~ lines will consist of three integers separated by a space: $H_i$ ~H_i~, $E_i$ ~E_i~, and $P_i$ ~P_i~.

The last line of input will consist of $s$ ~s~, the amount of time, in seconds, that you have until the Staff Meeting begins. You do not necessarily have to visit each teacher.

Output Specification

The first line of output should consist of the maximum total happiness possible for the video.

The second line of output should contain the minimum duration of the video for the maximum happiness level.

Constraints

$1 \le n \le 50$ ~1 \le n \le 50~

$1 \le E_i \le H_i \le 100$ ~1 \le E_i \le H_i \le 100~

$1 \le P_i \le 1\,000$ ~1 \le P_i \le 1\,000~

$1 \le s \le 1\,000$ ~1 \le s \le 1\,000~

Sample Input

Sample Output

170
4

Explanation for Sample Output

The first teacher contributes to the total happiness by $80$ ~80~ and adds to the preparation time by $20$ ~20~. The second teacher contributes by $90$ ~90~ and adds to the production time by $30$ ~30~. Adding these, we obtain $170$ ~170~, the maximum possible total happiness of the $4$ ~4~ second video, which is also the minimum duration for the maximum happiness level.

Comments

1

Xue_Alex commented on July 6, 2017, 2:45 a.m. ← edited →

"you assign a preparation time, Pi which is the time it takes for them to prepare for every second they appear plus that one second."

If this remains true, why is it that in the sample in/out 20 + 10 +10 + 10 +5 doesn't go over the 50 second limit, because wouldn't you need to add 1 second for each to account for the teacher being in the video?

edit: i cant read

2

Jackzhang commented on July 29, 2015, 3:39 a.m.

wait why is it 31 tho..

2

xXxP0t4t0MStRxXx commented on Sept. 25, 2016, 12:49 a.m.

Yea the sample case doesn't make any sense

2

TheZombieCloud commented on Sept. 30, 2016, 10:41 p.m.

Agreed. Author should fix sample case.

2

Kevin_Pan commented on Oct. 1, 2016, 10:12 p.m. ← edited →

For every second the $i^{th}$ ~i^{th}~ teacher is in the video he or she loses $E_i$ ~E_i~ of their happiness

31 + (31 - 1) + (31 - 2) = 90 minutes

2

xXxP0t4t0MStRxXx commented on Oct. 1, 2016, 11:02 p.m.

ahhhh... i totally misunderstood the question