В стране Мегаполия уже подходит время проведения олимпиады Мегаполисов, и все члены жюри должны собраться в главном городе страны — Мегаполисе, чтобы подготовить задачи соревнования.
Всего в стране есть n + 1 городов, пронумерованных числами от 0 до n. Город 0 — Мегаполис, в этом городе должны собраться все члены жюри. В городах с номерами от 1 до n живут члены жюри олимпиады, по одному в каждом городе. Подготовка олимпиады — долгий и ответственный процесс, занимающий k дней. Все эти k дней в работе над олимпиадой должны принимать участие все n членов жюри, и все они должны для этого быть в Мегаполисе во время подготовки.
Вам известно расписание ближайших рейсов (жюри олимпиады — люди серьёзные, а потому только летают самолётами). Все полёты в Мегаполии осуществляются только в Мегаполис и из него. В день своего прилёта и отлёта член жюри занят дорогой и не может участвовать в обсуждении олимпиады. Все рейсы в Мегаполии вылетают и прилетают в один и тот же день.
Собрать всех членов жюри вместе на k дней в столице — задача сложная, потратить при этом минимальное количество денег — почти невозможная. Тем не менее вам нужно найти самый дешёвый способ сначала собрать в Мегаполисе всех членов жюри, чтобы они могли работать вместе k дней, а затем отправить их обратно в родные города. Стоимостью способа называется суммарная стоимость билетов на все необходимые рейсы. При этом каждый член жюри в отдельности может пребывать в Мегаполисе и больше k дней.
Выходные данные
Выведите одно целое число — стоимость самого дешёвого способа собрать всех членов жюри в городе 0 на k дней и затем вернуть их всех в родные города.
Если собрать всех на k дней в Мегаполисе, а затем отправить всех обратно по домам невозможно, выведите «-1» (без кавычек).
Примечание
В первом примере оптимальный способ собрать всех в Мегаполисе — использовать рейсы, выполняемые в дни 1, 2, 8 и 9. Единственный альтернативный вариант, который заключается в том, чтобы отправить члена жюри из второго города домой в день 15, будет на 2500 дороже.
Во втором примере невозможно отправить домой из Мегаполиса члена жюри из города 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 6 5
1 1 0 5000
3 2 0 5500
2 2 0 6000
15 0 2 9000
9 0 1 7000
8 0 2 6500
|
24500
|
|
2
|
2 4 5
1 2 0 5000
2 1 0 4500
2 1 0 3000
8 0 1 6000
|
-1
|