Лікар призначив Степану \(N\) видів ліків. Протягом наступних \(a_i\) днів (включаючи день виписки рецепта) він повинен прийняти \(b_i\) таблеток \(i\)-го препарату. Йому не потрібно приймати жодних інших ліків.

Нехай день рецепта буде днем 1. У день 1 або після нього, коли наступить перший день, коли він повинен прийняти K або менше таблеток?

Обмеження

• \(1≤N≤3×10^5\)
• \(0≤K≤10^9\)
• \(1≤a_i ,b_i ≤10^9\)
• Усі вхідні значення є цілими числами.

Формат вхідних даних

Перший рядок містить цілі числа \(N,K\).

Наступні  \(N\) рядків містять цілі числа \(a_i, b_i\).

Формат вихідних даних

Якщо Степан має прийняти \(K\) або менше таблеток в день \(X\) вперше, то виведіть \(X\).

Приклад вхідних даних

4 8
6 3
2 5
1 9
4 2

Приклад вихідних даних

3

У 1-й день він повинен прийняти 3, 5, 9 і 2 таблетки 1-го, 2-го, 3-го і 4-го препарату відповідно. Загалом він має прийняти 19 таблеток у цей день, що не становить K(=8) таблеток або менше.

На 2-й день він повинен прийняти 3, 5 та 2 таблетки 1-го, 2-го та 4-го препарату відповідно. Загалом у цей день він повинен прийняти 10 таблеток, що не становить K(=8) таблеток або менше.

На 3-й день він повинен прийняти 3 і 2 таблетки 1-го і 4-го препарату відповідно. Загалом він має прийняти 5 таблеток у цей день, що становить K(=8) таблеток або менше перший раз.

Отже, відповідь 3.

Приклад вхідних даних

4 100
6 3
2 5
1 9
4 2

Приклад вихідних даних

1

Приклад вхідних даних

15 158260522
877914575 2436426
24979445 61648772
623690081 33933447
476190629 62703497
211047202 71407775
628894325 31963982
822804784 50968417
430302156 82631932
161735902 80895728
923078537 7723857
189330739 10286918
802329211 4539679
303238506 17063340
492686568 73361868
125660016 50287940

Приклад вихідних даних

492686569