Тёма играет в одну очень интересную компьютерную игру.
Во время прохождения очередной миссии, персонаж Тёмы оказался на незнакомой планете. В отличие от Земли эта планета плоская и представима в виде прямоугольника \(n \times m\).
Персонаж Тёмы находится в точке с координатами \((0, 0)\), чтобы успешно завершить миссию ему необходимо живым добраться до точки с координатами \((n, m)\).
Пусть персонаж компьютерной игры находится в координате \((i, j)\). Каждую секунду, начиная с первой, Тёма может:
- либо воспользоваться технологией гиперпрыжка по вертикали, после чего его персонаж попадёт в координату \((i + 1, j)\) в конце секунды,
- либо воспользоваться технологией гиперпрыжка по горизонтали, после чего его персонаж попадёт в координату \((i, j + 1)\) в конце секунды,
- либо Тёма может не совершать гиперпрыжок, тогда его персонаж не будет перемещаться в течение этой секунды.
Пришельцы, что обитают на этой планете очень опасны и настроены враждебно. Поэтому они будут стрелять из своих рельсотронов \(r\) раз.
Каждый выстрел полностью простреливает одну координату по вертикали или горизонтали. Если в момент выстрела (в конце секунды) персонаж находится в зоне его поражения, то он умирает.
Так как Тёма посмотрел исходный код игры, он знает полную информацию о каждом выстреле — время, простреливаемую координату, а также направление выстрела.
За какое минимальное время персонаж может добраться до нужной точки? Если он обречён на смерть и не сможет добраться до точки с координатами \((n, m)\), выведите \(-1\).
Выходные данные
Для каждого набора входных данных выведите единственное число — минимальное время, за которое персонаж сможет добраться до координаты \((n, m)\), либо же \(-1\), если ему суждено погибнуть.
Примечание
В первом наборе входных данных персонаж может перемещаться следующим образом: \((0, 0) \rightarrow (0, 1) \rightarrow (0, 2) \rightarrow (0, 3) \rightarrow (0, 3) \rightarrow (1, 3)\).
Во втором примере входных данных персонаж не сможет выйти за пределы прямоугольника, который будет полностью простреливаться выстрелами на \(2\) секунде.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 3
4
1 2 0
2 2 1
3 2 2
4 1 1
3 3
6
2 1 0
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2
2 1
3
7 1 2
2 1 1
7 2 1
2 2
5
9 1 2
3 2 0
5 1 2
4 2 2
7 1 0
4 6
7
6 1 2
12 1 3
4 1 0
17 2 3
1 2 6
16 2 6
3 2 4
|
5
-1
3
6
10
|