Čā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!
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).
Teksta faila piloti.rez vienīgajā rindā jāizvada vesels skaitlis - mazākā iespējamā naudas summa, kas Čārlijam jāizdod pilotu algām.
| piloti.dat | piloti.rez |
4 5000 3000 6000 2000 8000 1000 9000 6000 |
19000 |
| piloti.dat | piloti.rez |
6 10000 7000 9000 3000 6000 4000 5000 1000 9000 3000 8000 6000 |
32000 |
| piloti.dat | piloti.rez |
6 5000 3000 4000 1000 9000 7000 11000 5000 7000 3000 8000 6000 |
33000 |