405084: GYM101778 E Rescue Haibara

Haibara is one of Conan's best friends. Conan sent her as a spy in order to discover the killer in one of his investigations. Haibara was on her first mission as a spy. Unfortunately, her mission did not go as planned, and she has been compromised. Haibara got panicked and she forgot what she learned from Conan. So, it is your time to help her to avoid arrest. Your task is to help Haibara find the best safe house for her based on her current situation. There are n safe houses around Haibara's location. The i^th house is d_i kilometers away from Haibara, and it contains m_i coins.

According to the manual, the best safe house must be at distance no more than x and must contain at least y coins. If there is more than one safe house satisfying these conditions, you must choose the nearest one. If there is more than one safe house at the same distance, you must choose the one that contains the biggest amount of coins. Finally, if there is more than one safe house satisfying all the previous conditions, you must choose the one with minimum index.

Do not forget that Haibara is in a real danger, so you must find the best safe house for her as soon as possible. Conan will be very happy if you rescue Haibara. Can you do this?

The first line contains an integer T (1 ≤ T ≤ 500), in which T is the number of test cases.

The first line of each test case contains three integers n, x, and y (1 ≤ n ≤ 500) (1 ≤ x, y ≤ 1000), in which n is the number of safe houses, and x and y are the values from the manual as described in the statement.

Then n lines follow, each line contains two integers d_i and m_i (1 ≤ d_i, m_i ≤ 1000), in which d_i is the distance to the i^th safe house, and m_i is the amount of coins it contains. Safe houses are numbered from 1 to n in the order given in the input.

For each test case, print a single line containing  - 1 if there is no suitable safe house for Haibara. Otherwise, print the index of the safe house you have chosen for her.

2
3 5 3
4 2
7 1
5 7
4 4 6
3 7
3 8
2 4
5 2

3
2

In the second test case, you need to find a safe house at distance no more than 4 and must contain at least 6 coins. You can choose the 1^st or 2^nd safe houses, but according to the manual, the 2^nd safe house is the most suitable.