В стену вбито \(n\) гвоздей, \(i\)-й гвоздь вбит в \(a_i\) метрах над землёй, к нему привязан один конец верёвки длины \(b_i\) метров. Все гвозди вбиты на разных высотах друг над другом. Один леденец привязан сразу ко всем веревкам. Леденец привязан к концу веревки, который не привязан к гвоздю.
Чтобы взять леденец его нужно опустить на землю. Для этого Рудольф может перерезать некоторые верёвки, по одной за раз. Помогите Рудольфу найти минимальное количество верёвок, которое необходимо перерезать, чтобы получить леденец.
На рисунке изображен пример первого теста:
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество веревок, которые нужно разрезать, чтобы леденец упал на землю.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
4 3
3 1
1 2
4
9 2
5 2
7 7
3 4
5
11 7
5 10
12 9
3 2
1 5
3
5 6
4 5
7 7
|
2
2
3
0
|