34599번 - Tim 다국어

Upravo su završili prvi u nizu izbora u ovoj super izbornoj, 2024. godini. U saboru je $150$ vrućih fotelja pa mandataru (budućem predsjedniku Vlade) za sastavljanje većine i pobjedničkog tima treba $76$ ruku. Svaka stranačka lista dobila je neki broj mandata i, barem u ovom zadatku, će svi zastupnici s neke liste, tj. stranke biti složni i zajedno se prikloniti vlasti ili oporbi. Ti se želiš umiliti svom šefu stranke i reći mu sve kombinacije stranaka od kojih se može sastojati nova većina. Ako dobro odradiš posao, možda i ti u sljedećoj rošadi postaneš ministar. Sretno!

U prvom je retku prirodan broj $N$ ($3 ≤ N ≤ 20$), broj listi na izborima.

U sljedećih $N$ redaka su redom riječ $S$, ime liste, te prirodan broj $X$ ($1 ≤ X ≤ 150$), broj mandata koje je ta lista dobila. Ime liste $S$ biti će riječ s najviše $5$ velikih slova engleske abecede.

Ukupan broj dobivenih mandata iznosit će $150$.

U prvom retku ispiši $K$, broj kombinacija stranaka koje mogu sastaviti vladu.

U sljedećih $K$ redaka ispiši, leksikografskim poretkom (abecednim redom) kombinacije stranaka koje zajedno imaju potreban broj mandata. Svaka kombinacija je predstavljena imenima stranaka redom kojim su se pojavile u ulazu, međusobno spojenih znakom “-” (minus).

Opis trećeg probnog primjera: Demokrati Roberta Kumerlea¹ osvojili su $49$ mandata kao i Stranka liposuktiranih i naočitih antifeministica, a Aco Tudum Favorit $52$ mandata. Sve kombinacije u kojima su barem dvije liste mogu sastaviti većinu.

¹ Referenca iz jedne od najboljih domaćih serija – Bitange i princeze (sezona 2, epizoda 4)