Masala #DMXZSJ6JTU

Xotira 32 MB Vaqt 1000 ms
14

Qaysarchalar

Kechki soat 16:40. 20 daqiqadan keyin bolalarni o'z uyiga olib ketishadi. Bog'chadagi tarbiyachining e'tiborsizligi tufayli bolalar bir-birining sumkasini taqib olishdi. Endi har bir bolaga o'zining sumkasini berish kerak. Ammo buning uchun hammani so'mkasini yig'ib olib qaytadan tarqatishning imkoni yo'q, ya'ni bolajonlar so'mkasiz uyga jo'natishi mumkin deb o'ylashadi. Shu sababli bog'cha tarbiyachisi barcha bolalarning so'mkasi o'zida bo'lib qolmaguniqa qadar xoxlagan marotaba ixtiyoriy ikkita bo'lani yoniga chaqirib ularning so'mkasini almashtiradi. Bu amalni bajarishda bog'cha tarbiyachisi almashtirilayotgan so'mkalarning vaznlari yig'indisicha energiya sarflaydi. Kun kech bo'lgani uchun tarbiyachi juda charchagan, shu sababli iloji boricha kamroq energiya sarflagan holda barcha bolaga o'z sumkasini bermoqchi. Bog'cha tarbiyachisi barcha bolaga o'zining so'mkasini berishi uchun eng kamida qancha energiya sarflashini aniqlang.


Kiruvchi ma'lumotlar:

Birinchi qatorda \(N(1 \le N \le 10^6)\) - bolalar soni kiritiladi.

Keyingi qatorda \(N\) ta butun son \(A_i(1\le A_i \le 10^4)\) - har bir sumka vazni.

Uchinchi qatorda \(N\) ta butun son \(B_i(1 \le B_i \le N)\) - har bir bolaning yelkasidagi sumka raqami kiritiladi.

So'nggi qatorda \(N\) ta butun son \(C_i(1\le C_i \le N)\) - har bir bolaning sumkasi raqami kiritiladi. Barcha \(i \neq j\) uchun \(B_i \ne B_j\) va \(C_i \ne C_j\) shart bajariladi. Ya’ni \(B\) va \(C\) massivlari \(1\) dan \(N\)  gacha sonlarning permutatsiyasi hisoblanadi.


Chiquvchi ma'lumotlar:

Barcha bolalar o'z sumkasiga ega bo'lishi uchun sarflanishi kerak bo'lgan minimal energiya miqdorini chop eting.


Misollar
# input.txt output.txt
1
8
197 170 124 180 128 163 188 140
2 5 7 8 1 3 6 4
5 6 1 8 2 4 7 3
1534
2
6
40 24 20 12 24 16
2 5 6 4 1 3
6 4 3 5 1 2
112