Pelissä on n mahdollista ostettavaa esinettä. Jokaisella esineellä on tietty hinta.

Lisäksi pelissä on m esineiden yhdistelmää. Jokaisesta yhdistelmästä saa tietyn palkkion. Kerran ostettua esinettä voi käyttää useassa yhdistelmässä.

Mikä on suurin mahdollinen tuotto, jonka voit saada yhdistelmien avulla? Voit olettaa, että sinulla on alussa riittävästi rahaa kaikkien esineiden ostamiseen.

Syöte

Ensimmäisellä rivillä on kaksi kokonaislukua n ja m: esineiden määrä ja yhdistelmien määrä. Esineet on numeroitu 1,2,\dots,n.

Seuraavalla rivillä on n kokonaislukua p_1,p_2,\dots,p_n: kunkin esineen hinta.

Tämän jälkeen tulee m yhdistelmän kuvausta. Jokaisen kuvauksen ensimmäisellä rivillä on kaksi kokonaislukua k ja x: yhdistelmän esineiden määrä ja yhdistelmän tuottama palkkio. Toisella rivillä on k kokonaislukua: yhdistelmään kuuluvat esineet.

Kaikissa yhdistelmissä 1 \le k \le d.

Tuloste

Tulosta ensimmäiselle riville suurin mahdollinen tuotto. Tulosta sen jälkeen esimerkki tavasta, jolla tuotto voidaan saavuttaa: ensin yhdelle riville esineiden määrä ja sitten toiselle riville kaikki esineet. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Esimerkki

Syöte:

4 3
5 7 1 6
2 8
1 2
2 7
1 3
3 5
2 3 4

Tuloste:

2
3
1 2 3

Selitys: Ostat esineet 1, 2 ja 3 hintaan 5+7+1=13. Näiden esineiden avulla saat muodostettua yhdistelmät \{1,2\} (tuotto 8) ja \{1,3\} (tuotto 7). Kokonaistuotto on 15-13=2, joka on suurin mahdollinen.

Osatehtävä 1 (16 pistettä)

• 1 \le n, m \le 20
• 1 \le p_i, x \le 100
• 1 \le d \le 10

Osatehtävä 2 (17 pistettä)

• 1 \le n, m \le 100
• 1 \le p_i, x \le 10^6
• d=1

Osatehtävä 3 (29 pistettä)

• 1 \le n, m \le 100
• 1 \le p_i, x \le 10^6
• 1 \le d \le 2

Osatehtävä 4 (38 pistettä)

• 1 \le n, m \le 100
• 1 \le p_i, x \le 10^6
• 1 \le d \le 20