Piloti

ID: piloti
Grūtība: 3/5
Laika limits: 1

Uzdevums

Čārlijs ir kļuvis par aviotransporta korporācijas īpašnieku, un, lai tā neizputētu, viņam nepieciešams pēc iespējas ātrāk samazināt izdevumus.

Korporācijā strādā N piloti (N ir pāra skaitlis). Ir nepieciešams izveidot N/2 apkalpes. Katra apkalpe sastāv no 2 pilotiem - kapteiņa un asistenta. Kapteinim ir jābūt vecākam par savu asistentu. Katrs pilots drīkst strādāt tikai vienā apkalpē. Katram pilotam ir līgums, saskaņā ar kuru viņš var saņemt vai nu kapteiņa algu, vai asistenta algu. Katram pilotam viņa kapteiņa alga ir lielāka par viņa asistenta algu. Taču ir iespējama situācija, ka apkalpē asistentam ir lielāka alga nekā viņa kapteinim.

Uzrakstiet programmu, kas aprēķina mazāko naudas summu, kādu Čārlijam nāksies izmaksāt pilotiem algās, pieņemot, ka Čārlijs ir izstrādājis optimālu pilotu izvietojumu apkalpēs!

 

Ievaddati

Teksta faila piloti.dat pirmajā rindā dots vesels pāra skaitlis N, 2 ≤ N ≤ 10,000, - Čārlija korporācijā strādājošo pilotu skaits.

Nākamajās N rindās dota informācija par pilotu algām. Rindas ir sakārtotas pēc pilotu vecuma, sākot ar jaunāko pilotu. Katrā no šīm N rindām doti divi ar tukšumsimbolu atdalīti veseli skaitļi X un Y, 1 ≤ Y < X ≤ 100,000, - vienam pilotam noteiktā kapteiņa alga (X) un asistenta alga (Y).

 

Izvaddati

Teksta faila piloti.rez vienīgajā rindā jāizvada vesels skaitlis - mazākā iespējamā naudas summa, kas Čārlijam jāizdod pilotu algām.

 

Piemērs

piloti.datpiloti.rez
4
5000 3000
6000 2000
8000 1000
9000 6000
19000
  
piloti.datpiloti.rez
6
10000 7000
9000 3000
6000 4000
5000 1000
9000 3000
8000 6000
32000
  
piloti.datpiloti.rez
6
5000 3000
4000 1000
9000 7000
11000 5000
7000 3000
8000 6000
33000

 

Atsauces

Uzdevums izmantots Horvātijas informātikas olimpiādē 2004.gadā
© 2001-2002 olimps! http://www.lio.lv/olimps/