Кола
Откако ги завршил сите обврски поврзани со техничката организација на МОИ, Киро, кој е член на Комисијата за натпревари на ЗИМ, е спремен да тргне на пат за Радовиш (од Скопје).
Киро има карта на која се претставени сите општини и патишта во Македонија. На картата се обележани должините на патиштата (сите патишта се двонасочни), и напорот кој треба да го вложи Киро за да помине одреден пат е еднаков на должината на тој пат.
За среќа, Киро има кола во која е инсталиран нов систем од фабриките во Бунарџик, кој и овозможува автоматски да се движи низ патиштата во Македонија. Кога колата се движи автоматски, Киро не вложува никаков напор во возењето. Бидејќи сеуште е во експериментална фаза, овој нов систем за автоматско движење има неколку недостатоци:
1. Системот за автоматско движење може да се вклучи најмногу K пати во еден ден, а при една употреба на системот може да се изминат најмногу L километри. Киро планира да патува само неколку часа, па горенаведените ограничувања (K и L) всушност важат за целото патување.
2. Поради специфичниот начин на ориентација на колата, Киро не може да го вклучи или исклучи системот за автоматско движење на пола пат - тој мора да го вклучува/исклучува во самите општини. На пример, Киро не може да го вклучи (или исклучи) системот на пола пат од Скопје за Велес - туку мора да го вклучи во Скопје, за потоа, колата, без никаков напор од негова страна, да го однесе во Велес. Слично, Киро не смее да си дозволи да го остави системот да работи доколку е свесен дека до следната општина има повеќе километри отколку што може да измине системот.
3. Постојат општини каде, поради организација на различни манифестации на денот на патувањето, се спроведува посебен режим на одвивање на сообраќајот. Киро, ако одлучи да помине низ некои од нив, задолжително треба, кога ќе дојде во таква општина, да го исклучи системот за автоматско движење (доколку тој претходно бил вклучен). Потоа, доколку е тоа потребно, тој може, во истата општина, да го нагоди системот со нови параметри и повторно да го вклучи (нормално, ако веќе не го користел K пати) и да продолжи со својот пат. Киро точно знае во кои општини важи посебен режим на одвивање на сообраќајот и тој ги има означено овие општини на својата карта. За вклучување и исклучување на системот за автоматско движење е потребен напор 0.
Напишете програма која ќе му помогне на Киро да определи со колку најмалку напор може да се стигне од Скопје до Радовиш.
Влез
Во првиот ред се запишани два цели броја: вкупниот број на општини N (2 <= N <= 100) и бројот на општини во кои се спроведува посебен режим на одвивање на сообраќајот X (1 <= X < N-1). Во влезните податоци, општините во кои се спроведува посебен режим се претставени со броевите од 1 до X, додека останатите општини се претставени со броевите од X+1 до N. Скопје (стартот) е означен со бројот 1, додека Радовиш (дестинацијата) е означен со бројот N.
Во вториот ред се запишани два цели броеви K и L. Притоа, K (1 <= K <= 8) означува колку најмногу пати може да се искористи системот за автоматско движење, додека L (1 <= L <= 450) означува колку најмногу километри можат да се поминат при една употреба на системот.
Во третиот ред е запишан еден цел број M (1 <= M <= 200) кој го означува бројот на патишта. Во наредните M редови се запишани по три цели броја Si, Ei (1 <= Si, Ei <= N, Si е број различен од Ei) и Di (1 <= Di <= 90), кои означуваат дека постои двонасочен пат од општината Si до општината Ei, со должина Di. Две општини може да се поврзани со најмногу еден од овие директни двонасочни патишта.
Забелешка: Во тест случаи кои вредат најмалку 30% од поените, ќе важи (3 <= N <= 50) и K ќе биде еднакво на 1.
Излез
Излезот се состои од еден ред во кој треба да го отпечатите бараниот минимален напор. Секогаш ќе постои начин Киро да стигне до Радовиш.
Ограничувања
Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes
Примери
влез 9 5 3 10 10 1 5 5 9 8 3 2 5 5 2 3 4 2 6 11 7 4 5 8 7 4 6 4 3 7 9 30 3 4 12 | излез 17 |
Објаснување: Има 5 општини во кои се спроведува посебен режим на одвивање на сообраќајот (1, 2, 3, 4 и 5). Киро ќе се движи на следниот начин: 1->5->2->6->4->7->8->9. Системот за автоматско движење ќе се користи на патиштата 1->5, 5->2 и 4->7->8. Резултатот е 17 (11 + 3 + 3).
На сликата, со стрелки е обележан оптималниот пат. Со сина боја е обележан делот кој се поминува со напор 0.