B. Алис, Боб, Хоёр баг

хугацааны хязгаарлалт 1.5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Алис Боб хоёр тоглоом тоглож байна. Тоглоом нь тоглоомын хэсгүүдийг хоёр багт хуваах маягаар үргэлжилнэ. Тоглоомын $n$ хэсэг байх ба $i$-р хэсэг $p_{i}$ хүчтэй.

Тоглоомын хэсгүүдийг салгах зам нь хэд хэдэн алхамтай:

  1. Эхлээд Алис хэсгүүдийг $A$ ба $B$ гэсэн хоёр групп-д салгана. Энэ нь хэсгүүдийг $n$ урттай тэмдэгт мөрийг ашиглан хоёр багт хуваах ба тэмдэгт бүр $A$ эсвэл $B$ байна.
  2. Боб дурын угтвар (тэмдэгт мөрийн хамгийн эхний тэмдэгтийг агуулсан дэд тэмдэгт мөр) эсвэл дагавар (тэмдэгт мөрийн хамгийн сүүлийн тэмдэгтийг агуулсан дэд тэмдэгт мөр) сонгох ба уг дагаварын тэмдэгт бүрийг эргүүлнэ ($A$-г $B$ харин $B$-г $A$ болгоно).
  3. Алис бүх $A$ тэмдэглэгээтэй хэсгүүдийг авах бол Боб бүх $B$ тэмдэглэгээтэй хэсгүүдийг авна.

Тоглогчийн хүч нь групп дахь бүх хэсгийн хүчний нийлбэр юм.

Өгөгдөлд Алисийн хуваасан хоёр баг байгаа ба Бобд хамгийн тохиромжтой аргыг тодорхойлоход туслана уу. Бобын цуглуулж чадах хамгийн их хүчийг буцаа.

Оролт

Эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 5*10^{5}$) байх ба тоглоомын хэсгүүдийн тоо юм.

Хоёр дахь мөрөнд $n$ ширхэг бүхэл тоон утга $p_{i}$ ($1 ≤ p_{i} ≤ 10^{9}$) байх ба тус бүрдээ $i$-р хэсгийн хүч.

Гурав дахь мөрөнд $A$ болон $B$-с тогтсон $n$ ширхэг тэмдэгт байх ба эхний алхмын дараах багуудын сонголт (Алисын үйлдлийн дараах).

Гаралт

Бүхэл тоон утга $a$-г хэвлэх ба энэ нь Бобын олж авч чадах хамгийн их хүч юм.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
5
1 2 3 4 5
ABABA
Гаралт
11
Оролт
5
1 2 3 4 5
AAAAA
Гаралт
15
Оролт
1
1
B
Гаралт
1

Тэмдэглэл

Эхний жишээн дээр нэг урттай дагаварыг сонгож эргүүлэх хэрэгтэй.

Хоёр дахь жишээн дээр Боб $5$ урттай угтвар эсвэл дагаварыг (энд адилхан) сонгох хэрэгтэй.

Гурав дахь жишээн дээр Боб юу ч хийх хэрэггүй.

Сэтгэгдлүүдийг ачааллаж байна...