Uzb Eng

0004. Taksi
: 2 c
: 64

Uzoq davom etgan majlisdan song firma direktori xodimlarni uyiga olib borish uchun taksi buyurtma berishga qaror qildi. U xodimlar soniga teng bolgan N ta taksiga buyurtma berdi. Xodimlar uyiga kelganlarida song har bir taksi uchun 1 kilometr masofa uchun oz tariflari borligi malum boldi.
Direktor har bir xodimni ishdan uyigacha bolgan masofani biladi (lekin har bir xodim har xil yonalishli joylarda yashashadi, yani ikkita xodimni bitta taksida jonatishni imkoni yoq). Endi direktor qaysi xodimni qaysi taksida uyiga jonatish muammosi turibdi. Shunday jonatish kerakki, jami taksiga tolangan summa eng minimal bolsin.

:
Firmadagi xodimlar sonini bildiruvchi N (1≤N≤1000) soni berilgan (oz navbatida taksilar soni ham shuncha). Keyingi satrda xodimlarni ishdan to uyigacha bolgan masofani bildiruvchi N ta son berilgan (birinchi son birinchi xodimniki, ikkinchi - ikkinchi xodimniki va h.). Masofalar 1000km dan oshmaydi. Keyingi satrda taksilarni bir kilometr uchun tarifni bildirivchi N ta son berilgan (birinchi son birinchi taksiniki, ikkinchi - ikkinchi taksiniki va h.). Tariflar butun son bolib, 10000 dan oshmaydi.

:
N ta son chiqaring. Birinchi son - birinchi xodim otirgan taksi nomeri, Ikkinchi son - ikkinchi xodim otirgan taksi nomeri va h.. Taksiga tolangan son eng minimal bolishi lozim.

3
10 20 30
50 20 30

5
10 20 1 30 30
3 3 3 2 3
1 3 2



5 1 3 2 4
:
:


Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.