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, ... N-1, N in increasing order of distance from city 0.
The distance between cities i and i-1 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 re-embersed, 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

Source: codechef | Difficulty: HARD
Tags: Greedy algorithms

Sorting

Complete search


Solutions:
INFTY = 100000000

def find_num_days(price_threshold):
	curr_pos = 0
	took_days = 0
	while curr_pos < total_cities:
		(can_move, cum_dist) = (0, 0)
		while curr_pos + can_move < total_cities and cum_dist + dists[1 + can_move + curr_pos] <= max_day_dist:
			can_move += 1
			cum_dist += dists[can_move + curr_pos]
		while curr_pos + can_move < total_cities and can_move > 0 and (costs[curr_pos + can_move] > price_threshold):
			can_move -= 1
		if can_move == 0:
			return INFTY
		curr_pos += can_move
		took_days += 1
	return took_days
tests = int(input())
for _ in range(tests):
	(total_cities, max_day_dist) = [int(x) for x in input().split()]
	(dists, costs) = ([None] * (total_cities + 1), [None] * (total_cities + 1))
	for i in range(total_cities):
		(d_i, c_i) = [int(x) for x in input().split()]
		dists[i + 1] = d_i
		costs[i + 1] = c_i
	L = find_num_days(price_threshold=total_cities + 1)
	(low, high) = (min(costs[1:]) - 1, max(costs[1:]) + 1)
	while high - low > 1:
		mid = (low + high) // 2
		if L < find_num_days(price_threshold=mid):
			low = mid
		else:
			high = mid
	ans = high
	print(L, ans)