Сегодня в Берляндии проходят автогонки. Трасса представляет собой прямую дорогу длиной s километров. В гонке участвует n машин, все они стартуют одновременно в самом начале трассы. Для каждой машины известно ее поведение во время гонки — система отрезков, на каждом из которых скорость машины постоянна. j-ый отрезок у i-ой машины — пара (vi, j, ti, j), где vi, j — скорость машины на всем отрезке в километрах в час, ti, j — сколько часов машина ехала с такой скоростью. Отрезки заданы в последовательном порядке.
Ваша задача — выяснить, сколько обгонов произошло за время гонки. Обгоном считается ситуация, когда одна машина догоняет и опережает другую. Известно, что все обгоны происходят мгновенно, то есть не существует отрезка времени положительной длины, в течение которого какие-то две машины едут «вместе». В один момент времени в одной и той же точке на трассе может произойти несколько обгонов. В этом случае их все следует учитывать отдельно. Встречи машин на старте и на финише не считаются обгонами.
Выходные данные
Выведите одно число — количество обгонов, произошедших во время гонки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 33
2 5 1 2 14
1 3 11
|
1
|
|
2
|
2 33
2 1 3 10 3
1 11 3
|
0
|
|
3
|
5 33
2 1 3 3 10
1 11 3
2 5 3 3 6
2 3 1 10 3
2 6 3 3 5
|
2
|