TR-M2. Qo‘shni bo‘lmagan sinflar

Litsey sinflari «do‘st sinflar» daraxtini tashkil qiladi: n ta sinf, n − 1 ta do‘stlik. i-sinfda aᵢ ta o‘quvchi bor. Musobaqaga bir nechta sinf tanlanadi, lekin do‘st sinflar ikkalasi birga tanlanmaydi (bir-birini qo‘llab-quvvatlashlari kerak).

Tanlangan sinflardagi o‘quvchilar soni eng ko‘pi bilan nechta bo‘lishi mumkin?

Kirish ma’lumotlari

Birinchi qatorda n, ikkinchisida a₁ … aₙ. Keyingi n − 1 qatorda do‘stlik u v.

Chiqish ma’lumotlari

Bitta son — eng katta yig‘indi.

Cheklovlar

1 ≤ n ≤ 2·10⁵; 0 ≤ aᵢ ≤ 10⁹. Javob 32 bitga sig‘maydi.

1-misol: 1-sinf (10) markazda, barglar 4 + 4 + 4 = 12 > 10 — barglarni olamiz.