Nosaukums
Lampu izslēgšana (power)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
100%

Definīcija

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ā!


Ievaddatu raksturojums

Ievaddatu 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ē.


Izvaddatu raksturojums

Izvaddatu 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.


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2001.gadā


Paraugdati

Stdin
3
2
1 4
6 5
9 7
Stdout
65

Stdin
4
3
2 2
5 8
6 1
8 7
Stdout
56

Stdin
6
5
3 2
11 10
12 18
13 19
15 15
17 19
Stdout
370

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.