ŠIOM — League Of Legends

Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: leagueoflegends.in

Rezultatų failas: leagueoflegends.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

League Of Legends

Justas yra populiaraus žaidimo "League of Legends" žaidėjų komandos lyderis. Justo komanda ruošiasi turnyrui, todėl jis nori išanalizuoti kokius žaidimo herojus geriausia pasirinkti prieš pradedant mačą.

League of Legends žaidimo mače dalyvauja dvi komandos ir kiekviena jų mačo pradžioje turi pasirinkti tam tikrus herojus, kuriais žais. Taipogi, vieną herojų galima galima pasirinkti tik vieną kartą net tarp skirtingų komandų.

Kiekvieno mačo pradžioje komandos kapitonai parenka herojus vykdydami vieną iš dviejų veiksmų pagal duotą veiksmų tvarką. Veiksmai gali būti dviejų tipų: pasirinkti herojų arba uždrausti herojų.

Pasirinkti herojų - kapitonas pasirenka vieną iš galimų herojų, kuris atitenka jų komandai. Pasirinktas herojus daugiau nebegali būti pasirinktos jokios komandos.
Uždrausti herojų - kapitonas uždraudžia vieną herojų ir jo nebegali pasirinkti jokia komanda.

Kapitonas gali praleisti savo veiksmą. Tuo atveju, jei jis turėjo pasirinkti herojų, jo komandai atiteks atsitiktinis galimas herojus. Jei jis turėjo uždrausti herojų, joks herojus nėra uždraudžiamas.

Justas turi iš anksto susirašęs kiekvieno herojaus galingumą. Taipogi, Justas žino herojų pasirinkimų ir uždraudimų eiliškumą.

Komandos galingumas apskaičiuojamas kaip visų komandos pasirinktų herojų galingumų suma. Padėkite Justui sužinoti, kuri komanda bus galingesnė, jei abiejų komandų kapitonai herojus rinksis optimaliai gerai.

Pradiniai duomenys

Pirmoje eilutėje duotas vienas skaičius $n$ ( $1\\leqn\\leq100$ ) - herojų skaičius žaidime.

Antroje eilutėje yra $n$ skaičių s_i ( $1\\leqs_i\\leq10^6$ ) - $i$ -tojo herojaus galingumas.

Trečioje eilutėje duotas vienas skaičius $m$ ( $2\\leqm\\leqmin(n,20)$ ) - veiksmų skaičius, kuriuos turės įvykdyti komandų kapitonai.

Sekančiose $m$ eilučių duota po $2$ skaičius $v_i,k_i$ ( $1\\leqk_i\\leq2$ ) - $v_i$ nusako kokį veiksmą turi atlikti $k_i$ -tosios komandos kapitonas. Jei $v_i$ yra 'p', tai kapitonas turi pasirinkti herojų, o jeigu 'b', tai uždrausti herojų.

Garantuojama, jog abi komandos pasirinks bent po vieną herojų. Taip pat abi komandos galės pasirinkti bei uždrausti po lygiai herojų.

Rezultatai

Išveskite vieną skaičių - skirtumą tarp pirmos ir antros komandų galingumų jei abi komandos rinksis herojus optimaliai gerai.

Pavyzdžiai

Pradiniai duomenys	Rezultatai
4 1 2 3 4 4 p 2 b 2 p 1 b 1	-2

Šeštadieninė informatikos olimpiadininkų mokykla

League Of Legends

Pradiniai duomenys

Rezultatai

Pavyzdžiai