E. Багц худалдан авах

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

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

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

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

Арван зургаатын тооллын системийн вирус багц тоог задалж, нийлүүлж тоглох дуртай. Нэгэн гайхалтай өдөр тэрээр өөрийнх нь тэжээвэр муур Скуззи бүх багцийг нь нийлүүлээд нийлбэрийг нь идчихсэн байхыг олоод ихэд балмагдав. Яаралтай ямар нэг зүйл хийх шаардлагатай байсан учир тэрээр зах руу яаран гүйв.

Зах дээр $n$ ширхэг багц тооны хямдрал зарласан байв. Вирус дараах багцын цуглуулгыг худалдаж авахыг хүсчээ: цуглуулга дахь багцын цифрүүд нь бүх худалдан авсан багцын нэгдэл дэх тоонуудын цифртэй тэнцүү байх ёстой байв. Мөн тэрээр хамгийн боломжит хямд цуглуулгыг худалдан авахыг хүсэв.

Гэвч энэ нь тийм ч хялбар биш байв. Мэйнпрэйм нь цэвэр өрсөлдөөний талбар учир дурын $k$ багцын нэгдэл нь өөр хоорондоо ялгаатай $k$-ээс их тоо агуулна гэдгийг бид мэднэ (эерэг утгатай $k$ бүхэл тоо бүрт).
Вируст боломжит багцын цуглуулга худалдан авахад тусална уу. Цуглуулга хоосон байж болно.

Оролт

Эхний мөр нь $n$ ($1 ≤ n ≤ 300$) гэсэн ганц бүхэл тоо агуулах ба энэ нь зах дээр байгаа боломжит багцын тоо юм. Дараагийн $n$ мөр нь барааг тайлбарлана. Эхлээд бидэнд $m_{i}$ ($1 ≤ m_{i} ≤ n$) өгөгдсөн ба энэ нь $i$ дахь багцын ялгаатай цифрүүдийн тоог илэрхийлнэ. Дараагийн $m_{i}$ тоо нь багцын элементүүдийг харуулна. Багцын элементүүд нь өөр хоорондоо ялгаатай $n$-ээс эерэг бүхэл тоо байна.

Сүүлийн мөр нь багц бүрийн үнийг илэрхийлсэн $n$ ширхэг бүхэл тоо агуулах ба үүнийг абсолют утга нь $10^{6}$-ээс хэтрэхгүй байна.

Гаралт

Вирус $k$ багцын цуглуулгад төлөх хамгийн бага үнийг харуулсан ганц тоо гарга. Цуглуулгын багцын нэгдэл нь өөр хоорондоо ялгаатай яг $k$ ширхэг цифр байна.

().

Орчуулсан: Энхгэрэл

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

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