Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Paskaitų tvarkaraštis

Fakultete, kuriame Jonas mokosi, yra C\\timesT paskaitų, paskirstytų į C kategorijų po T paskaitų. Dienos pradžioje vienu metu įvyksta visos pirmos kategorijos paskaitos; po jų vienu metu vyksta visos antros kategorijos paskaitos ir t.t. Jonas turi išklausyti po vieną paskaitą iš kiekvienos kategorijos. Jis nori pasirinkti tokias paskaitas, kad studijoms reikėtų kuo mažiau energijos.

i-osios kategorijos j-oji paskaita reikalauja E_{ij} energijos. Paskaitos vyksta klasėse, kurios turi sveikas koordinates L ilgio koridoriuje (nuo 0 iki L). i-osios kategorijos j-oji paskaita vyksta klasėje, kurios koordinatė yra P_{ij}. Jonas ryte ateina į koordinatę 0, pagal pasirinktą tvarkaraštį vaikšto į paskaitas, galiausiai išeina iš fakulteto koordinatėje L. Atstumo d ėjimas reikalauja d energijos.

Pradiniai duomenys

Pirmoje eilutėje yra trys sveikieji skaičiai C, T ir L (1\\leC\\le25; 1\\leT\\le1000; 1\\leL\\le1000000).

Tolesnėse C\\timesT eilutėse yra po du sveikuosius skaičius, P_{ij} ir E_{ij} (0\\leP_{ij}\\leL; 0\\leE_{ij}\\le1000000). Pirmosios T eilutės aprašo pirmos kategorijos paskaitas, tolesnės - antros kategorijos, ir t.t. Vienoje kategorijoje esančios paskaitos turi skirtingas klasių koordinates.

Rezultatai

Vienintelėje eilutėje pateikite mažiausią reikalingą energijos kiekį.

Pavyzdys

Duomenys Rezultatai 
3 2 5
2 1
3 1
4 1
1 3
1 4
3 2
 
11