#abc305h. [abc305_h]Shojin
[abc305_h]Shojin
Problem Statement
You have decided to practice. Practice means solving a large number of problems in AtCoder.
Practice takes place over several days. The practice for one day is carried out in the following steps.
- Let be the number of problems to be solved on that day. Each problem has a value called difficulty, which is a pair of non-negative integers .
- First, rearrange the problems in any order. Then, solve the problems one by one in that order.
- You have a value called fatigue. The fatigue at the beginning of the day is , and it changes from to when solving a problem with difficulty .
- The fatigue at the end of solving all problems is called the energy consumed for that day.
There is a sequence of problems in AtCoder, called problem , problem , , problem in order. The difficulty of problem is .
You have decided to solve all problems through practice.
Practice is carried out in the following steps. Below, let denote the following sequence of problems: problem , problem , , problem .
- Choose an integer freely between and , inclusive. The practice will last days.
- Divide the sequence of problems into non-empty continuous subsequences, and let be the -th sequence.
Formally, choose a strictly increasing non-negative integer sequence such that and , and let S_i = for . - Then, for , solve all problems in on the -th day of practice.
You have decided to practice so that the total energy consumed throughout the practice is at most .
Let be the minimum possible value of , the number of days, for such a practice. (Here, it is guaranteed that . Under this constraint, such always exists.)
Also, let be the minimum possible total energy consumed throughout a practice such that .
Find and .
Constraints
- All input values are integers.
Input
The input is given from Standard Input in the following format:
Output
Print and separated by a space.
Sample Input 1
Sample Output 1
In this test case, you can solve all problems in one day while satisfying the condition for .
By following the steps below, the total energy consumed during the practice will be , which is the minimum.
- Set and solve on the first day.
- Carry out the practice on the first day in the following steps.
- Arrange the problems in the order (problem , problem , problem ).
- Initially, the fatigue is .
- Solve problem . The fatigue changes to .
- Solve problem . The fatigue changes to .
- Solve problem . The fatigue changes to .
- The fatigue at the end of solving all problems is . Therefore, the energy consumed on this day is .
- The total energy consumed throughout the practice is also .
Sample Input 2
Sample Output 2
This test case is obtained by changing from to in the first test case. Therefore, it is impossible to solve all problems in one day while satisfying the condition for .
By following the steps below, you can achieve by practicing for two days.
- Set , and solve on the first day and on the second day.
- Carry out the practice on the first day in the following steps.
- Arrange the problems in the order (problem , problem ).
- Initially, the fatigue is .
- Solve problem . The fatigue changes to .
- Solve problem . The fatigue changes to .
- The fatigue at the end of solving all problems is . Therefore, the energy consumed on the first day is .
- Carry out the practice on the second day in the following steps.
- Arrange the problems in the order (problem ).
- Initially, the fatigue is .
- Solve problem . The fatigue changes to .
- The fatigue at the end of solving all problems is . Therefore, the energy consumed on the second day is .
- The total energy consumed throughout the practice is .
Sample Input 3
Sample Output 3
The optimal practice is to solve one problem per day.