Masala #UVW7WUMNZF
Yangi yil sovg'asini tuzatish
Sizda n ta sovg'a bor va siz ushbu sovg'alarni bolalarga berishni xohlaysiz. Albatta, hech kimni ranjitishni xohlamaysiz, shuning uchun barcha sovg'alar bir xil bo'lishi kerak. i-sovg'a ai dona konfet va bi dona apelsindan iborat.
Bitta yurishda siz quyidagilardan birini tanlashingiz mumkin (1 ≤ i ≤ n):
- ai ni 1 ga kamaytirish (ya'ni, i-sovg'adan 1 dona konfet yeyish).
- bi ni 1 ga kamaytirish (ya'ni, i-sovg'adan 1 dona apelsin yeyish).
- ai va bi ni bir vaqtning o'zida 1 ga kamaytirish (ya'ni, i-sovg'adan 1 dona konfet va 1 dona apelsin yeyish).
Shuni ta'kidlash kerakki, siz konfet yoki apelsinni ularning miqdori 0 bo'lgan holatda yeyolmaysiz (ai va bi 0 dan kichik bo'lmasligi kerak).
Yuqorida aytib o'tilganidek, barcha sovg'alar bir xil bo'lishi kerak. Bu degani, quyidagi ikkita shart bajarilishi kerak:
- a1 = a2 = ⋯ = an
- b1 = b2 = ⋯ = bn
(ai va bi ning teng bo'lishi majburiy emas).
Sizning vazifangiz — barcha sovg'alarni tenglashtirish uchun zarur bo'lgan minimal yurishlar sonini topishdir.
Dastlabki qatorda bitta butun son t (1 ≤ t ≤ 1000) — testlar to'plami soni beriladi. Keyin esa t ta testlar to'plami keltiriladi:
- Har bir test uchun birinchi qatorda bitta butun son n (1 ≤ n ≤ 50) — sovg'alar soni.
- Ikkinchi qatorda n ta butun son a1, a2, ..., an (1 ≤ ai ≤ 10⁹) — har bir sovg'adagi konfetlar soni.
- Uchinchi qatorda n ta butun son b1, b2, ..., bn (1 ≤ bi ≤ 10⁹) — har bir sovg'adagi apelsinlar soni.
Har bir test uchun bitta butun son chiqaring: sovg'alarni tenglashtirish uchun zarur bo'lgan minimal yurishlar soni.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
5 3 3 5 6 3 2 3 5 1 2 3 4 5 5 4 3 2 1 3 1 1 1 2 2 2 6 1 1000000000 1000000000 1000000000 1000000000 1000000000 1 1 1 1 1 1 3 10 12 8 7 5 4 |
6 16 0 4999999995 7 |
Birinchi test to'plamida biz quyidagi yurishlar ketma-ketligini bajarishimiz mumkin:
- Birinchi sovg'ani tanlab, undan bitta apelsin yeyish, shunda a = [3, 5, 6] va b = [2, 2, 3] bo'ladi.
- Ikkinchi sovg'ani tanlab, undan bitta konfet yeyish, shunda a = [3, 4, 6] va b = [2, 2, 3] bo'ladi.
- Ikkinchi sovg'ani yana bir marta tanlab, undan bitta konfet yeyish, shunda a = [3, 3, 6] va b = [2, 2, 3] bo'ladi.
- Uchinchi sovg'ani tanlab, undan bitta konfet va bitta apelsin yeyish, shunda a = [3, 3, 5] va b = [2, 2, 2] bo'ladi.
- Uchinchi sovg'ani yana bir marta tanlab, undan bitta konfet yeyish, shunda a = [3, 3, 4] va b = [2, 2, 2] bo'ladi.
- Uchinchi sovg'ani yana bir marta tanlab, undan bitta konfet yeyish, shunda a = [3, 3, 3] va b = [2, 2, 2] bo'ladi.
Telegram kanalimizga obuna bo'ling