C. Таня ба тоглоомууд

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

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

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

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

Берландад саяхан тоглоомуудын шинэ цуглуулга хямдрал зарлажээ. Энэ цуглуулга нь $10^{9}$ төрлийн тоглоомуудаас тогтох ба эдгээр нь $1$-ээс $10^{9}$ хүртэл дугаарлагдсан байв. Шинэ цуглуулгын $i$-дахь төрлийн тоглоом нь $i$ боурле үнэтэй байна.

Таня шинэ цуглуулгаас ялгаатай $n$ төрлийн $a_{1}, a_{2}, ..., a_{n}$ тоглоомуудыг цуглуулахаар болжээ. Өнөөдөр Таня-ын төрсөн өдөр ба түүний ээж охиныхоо бэлэгт $m$-ээс ихгүй боурле зарцуулахаар шийджээ. Таня шинэ цуглуулгаас хэд хэдэн төрлийн тоглоомуудыг бэлэг болгон сонгох юм. Мэдээж хэрэг, тэрээр өөрт аль хэдийн байгаа төрлийн тоглоомоо сонгохыг хүсэхгүй.

Таня үр дүнд нь аль болох олон ялгаатай төрлийн тоглоомууд түүний цуглуулгад байхыг хүсэж байгаа. Шинэ цуглуулга нь хэтэрхий олон төрлийн ба Таня хэтэрхий жаахан, иймд тэрээр таныг үүнд туслахыг хүсжээ.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ ($1 ≤ n ≤ 100 000$) болон $m$ ($1 ≤ m ≤ 10^{9}$) өгөгдөнө -- эдгээр нь Таня-д аль хэдийн байгаа тоглоомын төрлийн тоо болон түүний ээж шинэ тоглоомууд авахад үрэхийг хүсэж байгаа боурле-ын тоог илэрхийлнэ.

Дараагийн мөрөнд ялгаатай $n$ ширхэг бүхэл тоо $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 10^{9}$) өгөгдөнө -- эдгээр нь Таня-д аль хэдийн байгаа тоглоомын төрлүүдийг илэрхийлнэ.

Гаралт

Эхний мөрөнд ганц бүхэл тоо $k$-г хэвлэнэ -- энэ нь түүний цуглуулга дахь ялгаатай төрлүүдийн тоглоомуудын тоо нь хамгийн их байхаар Таня-ын сонгох ёстой ялгаатай төрлүүдийн тоглоомуудын тоог илэрхийлнэ. Мэдээж хэрэг, сонгосон тоглоомуудын нийт үнэ нь $m$-ээс хэтрэх ёсгүй.

2-дахь мөрөнд зайгаар тусгаарлагдсан ялгаатай $k$ ширхэг бүхэл тоо $t_{1}, t_{2}, ..., t_{k}$ ($1 ≤ t_{i} ≤ 10^{9}$)-уудыг хэвлэнэ -- эдгээр нь Таня-ын сонгох ёстой тоглоомуудын төрлийг илэрхийлнэ.

Хэрэв олон хариулт байвал, та алийг нь ч хэвлэсэн болно. $t_{i}$-уудын утгуудыг ямар ч дарааллаар хэвлэж болно.

Орчуулсан: Баатархүү

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

Оролт
3 7
1 3 4
Гаралт
2
2 5 
Оролт
4 14
4 6 12 8
Гаралт
4
7 2 3 1

Тэмдэглэл

Эхний жишээнд ээж нь 2 тоглоом худалдаж авч өгөх ёстой: $2$-дахь төрлийн нэг тоглоом болон $5$-дахь төрлийн нэг тоглоом. $7$ боурле-ын бусад худалдан авалт болгонд ($1$, $3$ болон $4$-дэх төрлийн тоглоомуудыг аль хэдийн худалдан авсан гэж үзнэ) 2 болон түүнээс дээш тооны тоглоом худалдан авах боломжгүй байна.

Сэтгэгдлүүдийг ачааллаж байна...