Anh cần cho mình là một khoản tiền T đồng, và anh chọn cách bán những món hàng của mình. Anh có N món hàng, và có Q khách hàng sẵn sàng mua những món hàng của Anh. Người thứ i sẽ mua món hàng a[i] với giá là v[i] vào ngày thứ i. Món hàng nào đã bán cho khách thì Anh không thể bán lại cho khách khác được, và Anh có thể lựa chọn khách hàng nào để bán cho phù hợp với nhu cầu của mình. Anh muốn có số tiền sớm nhất có thể.

Hãy cho biết ít nhất Anh cần phải đợi đến ngày thứ bao nhiêu để có một khoản tiền không nhỏ hơn T.

Dữ liệu

• Dòng đầu chứa 3 số nguyên N, T, Q tương ứng với số món hàng của Anh, số tiền Anh cần để mua vé và số lượng khách mua hàng. (1 ≤N, Q ≤10000, 1 ≤T ≤10^7)

• Q dòng sau, mỗi dòng gồm 2 số nguyên, dòng thứ i chứa hai số nguyên ai và vi tương ứng với món hàng khách muốn mua với mức giá của nó.(1 ≤ai ≤N, 1 ≤vi ≤10^7)

Kết quả

Gồm một dòng duy nhất là là ngày sớm nhất mà Anh đủ tiền để mua vé. Nếu bán hết cho khách mà vẫn không đủ tiền thì xuất -1.

Sample Input

2 3 3
1 1
2 1
1 2

Sample Output

3

Sample Input

2 3 3
1 1
2 1
1 1

Sample Output

-1