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, to each teacher. For every second the teacher is in the video, the total happiness, , increases by .
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, , is assigned to each teacher. For every second the teacher is in the video he or she loses of their happiness, with a lower happiness bound of . 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, which is the time it takes for them to prepare for every second they appear plus that one second. That is, if of the 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.
The next line will consist of , the number of teachers in the school.
The next lines will consist of three integers separated by a space: , , and .
The last line of input will consist of , the amount of time, in seconds, that you have until the Staff Meeting begins. You do not necessarily have to visit each teacher.
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.
2 80 50 20 31 1 10 50
Explanation for Sample Output
The first teacher contributes to the total happiness by and adds to the preparation time by . The second teacher contributes by and adds to the production time by . Adding these, we obtain , the maximum possible total happiness of the second video, which is also the minimum duration for the maximum happiness level.