Одарённый невероятной магией и всезнанием Максимус заметил группу из
n монстров, приближающихся к городку Элдстейд. Своими волшебными способностями он мгновенно определил расстояние в километрах от города до каждого монстра. Он также заметил, что все монстры двигаются с постоянной скоростью. У Максимуса есть оружие, способное уничтожить одного монстра после полной зарядки. Зарядка занимает ровно одну минуту. Чтобы победить монстра, оружие должно быть полностью заряжено к моменту приближения монстра к городу. Другими словами, невозможно убить монстра достигшего города, даже если в этот момент оружие закончило полную зарядку.
Максимус задается вопросом, сможет ли он сам спасти город от всех монстров или ему нужна помощь.
Напишите программу, которая поможет Максимусу мгновенно определить максимальное количество монстров, которое он сможет уничтожить до того момента, как хотя бы один монстр достигнет города.
Входные данные
Первая строка содержит число n - количество монстров. Во второй строке записано
n чисел
dist[i] - начальное расстояние в километрах от города для
i-го монстра. Третья строка содержит
n чисел
speed[i] - скорость
i-го монстра в километрах в минуту.
Ограничения
n == длина массива dist == длина массива speed1 <= n <= 1051 <= dist[i], speed[i] <= 105
Выходные данные
Выведите ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
Примечание |
| 1 |
3
1 3 4
1 1 1
|
3
|
Вначале расстояния между монстрами равны [1,3,4]. Максимус уничтожает первого монстра.
Через минуту расстояния между монстрами становятся [X,2,3]. Максимус уничтожает второго монстра.
Через минуту расстояния между монстрами будут [X,X,2]. Максимус уничтожает третьего монстра.
Все три монстра могут быть уничтожены.
|
| 2 |
4
1 1 2 3
1 1 1 1
|
1
|
Вначале расстояния между монстрами равны [1,1,2,3]. Максимус уничтожает первого монстра.
Через минуту расстояния между монстрами становятся равными [X,0,1,2], и второй монстр достиг города.
Максимус может уничтожить только 1 монстра. |