Maigonis ir beidzot dabūjis interesantu un labi apmaksātu darbu. Katru rītu uz ciema galvenās ielas viņam ir jāizslēdz visas lampas. Visas lampas atrodas ielas vienā pusē un iela ir pilnīgi taisna.
Maigonis naktis pavada ballītēs un lampu izslēgšanu sāk tieši pulksten piecos no rīta. Maigonis lampu izslēgšanas sākuma brīdī atrodas tieši pretī vienai no tām.
Katrai lampai ir noteikta jauda, un, tā kā Maigonim simpatizē dabas aizsardzības idejas, viņš vēlas, lai kopējais lampu patērētais enerģijas daudzums (laikā kamēr viņš izslēgs visas lampas) būtu pēc iespējas mazāks.
Maigonis pēc nakts jūtas saguris, tāpēc pārvietojas ar ātrumu 1m/s. Lampas izslēgšana laiku neprasa, jo to var izdarīt garāmejot.
Uzrakstiet programmu, kas nosaka mazāko iespējamo enerģijas daudzumu lampu izslēgšanas laikā!
Teksta faila power.in pirmajā rindā dota naturāla skaitļa N (lampu skaits ciemā, 2 ≤N≤1000) vērtība. Lampas ir numurētas ar naturāliem skaitļiem no 1 līdz N pēc kārtas, sākot no ciema viena gala.
Faila otrajā rindā dota naturāla skaitļa V (1≤V≤N) vērtība - tās lampas numurs, pie kuras Maigonis sāk lampu izslēgšanu.
Katra no nākošajām N faila rindām satur divu veselu skaitļu D(0≤D≤1000) un W(0 ≤W≤1000) vērtības un apraksta vienu lampu. D ir lampas attālums no ciema gala (izteikts metros) un W ir lampas patērētā enerģija vienā sekundē.
Teksta faila power.out vienīgajai rindai jāsatur mazākais iespējamais patērētās elektroenerģijas daudzums lampu izslēgšanas laikā. Atrisinājuma vērtība nepārsniegs 109.
| power.in | power.out |
3 2 1 4 6 5 9 7 |
65 |
| power.in | power.out |
4 3 2 2 5 8 6 1 8 7 |
56 |
| power.in | power.out |
6 5 3 2 11 10 12 18 13 19 15 15 17 19 |
370 |