First Time Both Targets Are Met

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Two counters start at zero. At each 1-based step add nonnegative (x,y); find the earliest step when both totals meet A and B. If both thresholds are zero output 0, and if never met output -1.

Input

First n A B, followed by n pairs x_i y_i.

Output

Print earliest 1-based index, 0 if initially satisfied, or -1.

Subtasks

• Subtask 1 (20%): n ≤ 20, thresholds and increases ≤100.

• Subtask 2 (30%): n ≤ 1000, thresholds ≤10^9, increases ≤10^6.

• Subtask 3 (50%): n ≤ 100000, thresholds ≤10^12, increases ≤10^9.

Examples

Example 1

Input:

3 3 5
1 2
2 1
0 2

Output:

3

Explanation: The totals reach (3,5) for the first time at step 3.

Example 2

Input:

2 0 0
1 1
2 2

Output:

0

Explanation: Both thresholds are satisfied before the first step.