За последнее время Боб заметно растолстел. Чтобы похудеть, Боб решил заняться плаванием в бассейне, но перед тем как он пошёл в бассейн первый раз, ему приснился очень странный сон. Во сне Боб плыл по одной из дорожек бассейна, а в этом бассейне помимо Боба плавали медузы. Стоит ли говорить, что медузы всегда были одним из самых глубоких детских страхов Боба.
Для простоты, примем следующую физическую модель:
- Дорожка бассейна представляет собой часть плоскости, ограниченную прямыми \(x=0\) и \(x=w\). Боб не имеет права выплывать с дорожки, но может касаться её границы.
- Сами медузы очень маленькие, но во сне Боба они очень шустрые. У каждой медузы есть своя область активности в форме круга вокруг неё. У двух разных медуз зоны могут перекрываться или даже быть вложенными.
- Боб имеет форму выпуклого многоугольника.
- К сожалению, лишний вес сделал его совершенно неповоротливым, то есть плавание Боба представляет собой параллельный перенос. Но при этом в каждый конкретный момент времени направление этого переноса может быть любым.
- Если Боб заплывает в область активности медузы, она его замечает, догоняет и очень больно ужаливает. Считается, что Боб заплыл в область активности медузы, если в какой-то момент времени пересечение его многоугольника с этой областью имеет ненулевую площадь (в частности, если они только касаются, медуза не заметит Боба).
- Если медуза ужалила Боба, она довольная уплывает по своим делам и больше опасности не представляет.
Бобу нужно проплыть всю дорожку бассейна и быть ужаленным минимальное число раз. Он начинает движение на прямой \(y=-h\), а закончить должен на прямой \(y=h\), где \(h = 10^{10}\).
Выходные данные
Выведите одно число — минимальное число медуз, которые ужалят Боба, если он будет действовать оптимальным образом.
Примечание
Ниже вы можете увидеть визуализацию возможных решение первого и второго примера:

Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4 0 0 2 0 2 2 0 2 3 1 1 1 3 5 1 1 9 1
|
0
|
|
2
|
4 6 0 0 3 0 3 3 0 3 3 1 0 1 4 2 2 3 6 1
|
2
|
|
3
|
4 2 0 0 1 0 1 1 0 1 2 1 1 1 1 3 1
|
2
|