Ngưỡng hai chỉ tiêu (First Time Both Targets Are Met)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Hai chỉ tiêu có ngưỡng A và B, ban đầu tổng tích lũy của từng chỉ tiêu đều bằng 0. Lần thứ i bổ sung cặp không âm (x_i,y_i) vào hai tổng. Tìm chỉ số lượt nhỏ nhất tính từ 1 mà cả hai tổng đồng thời đạt hoặc vượt ngưỡng. Nếu A=B=0 thì đáp án là 0 trước mọi lượt; nếu sau n lượt vẫn thiếu một trong hai thì in -1. Khi đã đạt, các lượt sau không thay đổi đáp án.

Input

Dòng đầu n A B; tiếp theo đúng n cặp x_i y_i theo thứ tự thời gian.

Output

Một số nguyên: chỉ số nhỏ nhất, 0 hoặc -1 theo quy định.

Subtask

• Subtask 1 (20%): 0 ≤ n ≤ 20; 0 ≤ A,B ≤ 100; 0 ≤ x_i,y_i ≤ 100.

• Subtask 2 (30%): 0 ≤ n ≤ 1000; 0 ≤ A,B ≤ 10^9; 0 ≤ x_i,y_i ≤ 10^6.

• Subtask 3 (50%): 0 ≤ n ≤ 100000; 0 ≤ A,B ≤ 10^12; 0 ≤ x_i,y_i ≤ 10^9.

Ví dụ

Ví dụ 1

Input:

3 3 5
1 2
2 1
0 2

Output:

3

Giải thích: Sau lượt 2 tổng (3,3) còn thiếu chỉ tiêu B; lượt 3 được (3,5).

Ví dụ 2

Input:

2 0 0
1 1
2 2

Output:

0

Giải thích: Cả hai ngưỡng bằng 0, đã đạt trước lượt 1.