Balloonburst

Problem Description

You are given $n$ balloons inside a hall. The ceiling of the hall is at a height of $h$ meters. Each balloon initially floats at height $a_i$ meters and rises upward at a constant rate of $v_i$ meters per second. A balloon bursts the moment it reaches or exceeds the ceiling height $h$. You are also given a duration $t$ in seconds. Your task is to determine:

• How many balloons do not burst after $t$ seconds?
• Among the balloons that do not burst, print the index of the one that is at the maximum height. If multiple balloons have the same maximum height, choose the one with the largest index. If no balloons remain unburst, print 0 -1.

Input Format

The first line contains three integers $n$, $h$, and $t$ --- the number of balloons, the height of the ceiling, and the time in seconds. Each of the next $n$ lines contains two integers $a_i$ and $v_i$ --- the initial height and the upward velocity of the -th balloon.

Constraints:

• $1 \leq n, t \leq 10^5$
• $0 \leq a_i < h \leq 10^9$

Output Format

Print a single line containing two space-separated integers: the number of balloons that do not burst after $t$ seconds, and the index of the highest unburst balloon (or $-1$ if there are none).

Scoring

4 10 2
2 3
3 2
5 3
4 1

3 1

2 4 2
0 2
2 1

0 -1

2 5 2
0 2
2 1

2 2