$N$ con bò của Farmer John ($1 \le N \le 50{,}000$), đánh số $1..N$, định bỏ trốn vào rạp xiếc. Móng guốc khiến chúng không thể đi dây hay đu xà (lần cuối thử bắn bò từ đại bác cũng thất bại thảm hại). Vì vậy chúng luyện nhào lộn.

Chúng không sáng tạo lắm và chỉ nghĩ ra một trò: đứng lên nhau thành chồng thẳng đứng có độ cao nào đó. Chúng muốn tìm thứ tự trong chồng.

Mỗi con có trọng lượng ($1 \le W_i \le 10{,}000$) và sức mạnh ($1 \le S_i \le 1{,}000{,}000{,}000$). Nguy cơ ngã bằng tổng trọng lượng các con phía trên (không gồm chính nó) trừ sức mạnh, nên con khỏe hơn có nguy cơ thấp hơn. Hãy tìm thứ tự làm nhỏ nhất nguy cơ lớn nhất của mọi con.

Dữ liệu vào

• Dòng 1: số nguyên $N$.
• Các dòng $2..N+1$: dòng $i+1$ mô tả bò $i$ bằng hai số nguyên cách nhau bởi dấu cách $W_i$, $S_i$.

Dữ liệu ra

• Dòng 1: số nguyên là nguy cơ lớn nhất của mọi con trong bất kỳ thứ tự tối ưu giảm nguy cơ nào.

Ví dụ

Dữ liệu vào 1

3
10 3
2 5
3 3

Dữ liệu ra 1

2

Ghi chú

Đặt con nặng 10 ở dưới. Nó đỡ hai con kia, nên nguy cơ là $2+3-3=2$. Các con khác có nguy cơ thấp hơn.