E. Ахлагчийн горим

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

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

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

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

Костя бол Dota 2-оор мэргэшиж буй программер билээ. Тоглоомын хөгжүүлэгч Valve корпрациас саяхан тоглоомын эмх замбраагүй байдлыг тэнцвэржүүлсэн шинэ түр холболт гаргажээ. Костя бол багийнхаа ахлагч ба түүнд том үүрэг хариуцлага оногдож байгааг ухаарсан. Тиймээс тэрээр тоглоомын шинэчлэлтээс болж тоглолт бүрд хамгийн сайн баатруудыг өөрийнхөө багт математикийн шинжээр нь дахин зохион байгуулах хэрэгтэй болжээ.

Dota 2 нь хоёр багийг хамрана. Баг бүрийн тоглогчид өөрсдийн тоглох баатраа сонгох ба нэг баатрыг хэд хэдэн тоглож нэгэн зэрэг авах боломжгүй. Костягийн баг томоохон электроноик спортын тэмцээнд оролцох гэж байгаа бөгөөд уг тэмцээн нь Ахлагчийн горимоор явагдана. Энэ горимд ахлагч нь баатруудыг сонгоод "авах" юм уу "хасах" үйлдэл хийнэ. - Багтаа баатар авах. Ахлагч нь баатраа авсны дараа тухайн багийн гишүүд уг баатрыг сонгон авч тоглох боломжтой. Энэ үйлдийг тодорхой хугацааны дотор хийнэ. - Баатар хасах. Баатрыг хассаны дараа аль ч багийнхан тэр баатрыг сонгох боломжгүй болно. Энэ үйлдийг тодорхой хугацааны дотор хийнэ.

Багийн ахлагчид хасах болон авах сонголтондоо хугацаандаа амжилгүй алдаж болно. Хэрвээ авах сонголтоо алдвал тухайн агшинд боломжтой байгаа баатруудаас санамсаргүйгээр нэг баатрыг тэр багт өгнө. Харин хасах сонголтоо алдвал ямар ч баатар хасагдахгүй.

Костя шинэчлэлтийн дараах бүх баатрын хүчийг тодорхойлсон мөн тэрээр сонгох болон хасах дарааллыг мэдэж байгаа. Багийн хүч нь багийн баатруудын хүчний нийлбэрээр илэрхийлэгдэнэ. Оролцогчид багууд аль аль нь өөрсдийн багт байгаа давуу талын ялгааг хамгийн их байлгахыг хичээнэ. Костяад аль баг нь илүү давуу талтайг болон давуу тал нь хэр их болохыг тодорхойлоход тусална уу.

Оролт

Эхний мөрөнд Dota 2 дээрх баатрын тоо $n$ байна.

Хоёрдугаар мөрөнд баатруудын хүч болох $s_1$, $s_2$,..., $s_n\ (1≤ s_i ≤ 10^6)$ тоонууд байрлана.

Гуравдугаар мөрөнд ахлагчийн гүйцэтгэх үйлдлийн тоо болох $m$ $(2\ ≤\ m\ ≤\ min(n,\ 20))$ өгөгдөнө.

Дараагийн $m$ мөрөнд "үйлдэл баг" хэлбэрийн өгөгдлүүд байх ба үйлдэл нь сонгох ($p$-ээр тэмдэглэгдэнэ) юм уу хасах ($b$-ээр тэмдэглэгдэнэ), баг гэдэгт нь аль багийн гүйцэтгэл болохыг хэлнэ ($1$ юм уу $2$).

Багууд ядаж нэг нэг авах үйлдэл хийх ба 2 багийн авах үйлдэл хийх тоо адил мөн хасах үйлдэл хийх тоо ижил байна.

Гаралт

Хэрвээ хоёр багийн ахлагч хамгийн зөв сонголтыг хийсэн бол эхний баг болон 2-р багийн хүчний зөрүүг хэвлэ.

Орчуулсан: Говьхүү

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

Оролт
2
2 1
2
p 1
p 2
Гаралт
1
Оролт
6
6 4 5 4 5 5
4
b 2
p 1
b 1
p 2
Гаралт
0
Оролт
4
1 2 3 4
4
p 2
b 2
p 1
b 1
Гаралт
-2
Сэтгэгдлүүдийг ачааллаж байна...