Optimal Trip

All submissions for this problem are available.
Chef has decided to take a break, and go for a ride. He is currently in city 0, and he wants to get to city N.
The cities along the road from 0 to N are numbered 0, 1, 2, 3, ... N1, N in increasing order of distance from city 0.
The distance between cities i and i1 is denoted by d_{i}.
However, as is always the case, it is unsafe to travel at night, so he will have to break his journey over multiple days.
Chef may travel at most D distance in any day, so he will have to book hotel for overnight stay in some of the cities.
On any day, Chef will begin his journey from some city and end his journey at some other city.
Chef wants to reach city N in as few days as possible, so he has to plan his trip accordingly.
Let L be the minimum number of days in which he can reach city N.
Chef knows the cost of overnight stay in each city. The cost of overnight stay in city i is c_{i}.
Chef will need to get all his hotel bills reembersed, and his boss might get suspicious if cost for any single day exceeds a threshold.
Chef knows that his boss wants him to reach as soon as possible. Thus, if it is possible for Chef to go from 0 to N in L days with no restriction on where Chef stays, then his boss will want him to reach in exactly L days. However, if the boss puts a threshold value i then we know that the Chef may not be able to reach in L days (since he may not be allowed to stay at some hotels). Help him him find the minimum threshold value C such that if he only stays in hotels of cost <= C, it is possible for him to reach the destination N in exactly L days (remember, here L is the minimum number of days needed by Chef if there were absolutely no restrictions on where he stays).
Formally, let L be the minimal number of days it takes Chef to get from city 0 to city N. Let F(i) be the minimal number of days it takes Chef to get from city 0 to city N if it's not allowed to pay more than i for a single stay in hotel. Find the smallest C that will still allow Chef to get to city N without losing time. In other words F(C)=L. Find and output L as well.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case has two space separated integers N and D.
N lines follow, each having two space separated integers, d_{i} and c_{i}.
Output
For each test case, output a separate line containing the values of L and C.
Constraints
 1 ≤ T ≤ 15
 2 ≤ N ≤ 10^{5}
 1 ≤ D ≤ 10^{9}
 1 ≤ d_{i} ≤ D
 1 ≤ c_{i} ≤ N
 The sum of N over all test cases in any file is at most 4*10^{5}.
Subtack 1 (30 points)
N ≤ 10^{3}
Subtack 2 (30 points)
d_{i} = 1, D = 9
Subtask 3 (40 points):
No special constraints
Example:
Sample Input
2
4 5
2 4
1 2
3 3
1 1
5 6
2 1
4 4
2 2
2 3
4 5
Sample output
2 2
3 2
Explanation
For test case# 1, the optimal trip is 0 → 2 → 4
For test case# 2, the optimal trip is 0 → 1 → 3 → 5
Author:  utkarsh_lath 
Tester:  
Editorial  http://discuss.codechef.com/problems/TRIPCOST 
Tags  easy, greedy, ltime02, utkarsh_lath 
Date Added:  12072013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 