C. Таны гаргаж чадах утгууд

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

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

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

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

Пари Аря-аас нэгэн үнэтэй шоколад худалдан авахыг хүсжээ. Түүнд $n$ ширхэг зоос байгаа бөгөөд $i$-дахь зоос нь $c_{i}$ үнэтэй байв. Түүний худалдан авахыг хүсэж буй шоколадны үнэ нь $k$ ба иймд тэрээр өөрт байгаа зооснуудаас нийлбэр утга нь $k$ байх зооснуудын дэд олонлог сонгон авах бөгөөд үүнийгээ Аря-д өгөх юм.

Ийм байх зооснуудын хайж байхдаа түүний толгойд дараах бодол орж иржээ: эдгээр зооснуудыг Аря-д өгсний дараа Аря эдгээр зооснуудыг ашиглан ямар утгууд гарган авч болохыг тэрээр боджээ. Пари хувь хүний хувьд бага зэрэг атаархуу нэгэн учраас Аря-г тэдгээр зооснуудыг ашиглан олон утга гаргаж чадахгүй байхыг хүсэж байв. Иймд тэрээр Аря нийлбэр утга нь $k$ байх зооснуудын дэд олонлогийг ашиглан гаргаж чадах бүх $x$-ын утгуудыг мэдэхийг хүсжээ.

Илүү дэлгэрэнгүй хэлбэл, Пари өөрт байх зооснуудын нийлбэр утга нь $k$ байх зооснуудын дэд олонлогуудын хувьд тухайн дэд олонлогийн ямар нэгэн дэд олонлогийн нийлбэр утга $x$-ын бүх боломжит утгыг мэдэхийг хүсэж байв. Өөрөөр хэлбэл бид ямар нэгэн байдлаар шоколадыг худалдан авахад Аря тэдгээр зооснуудыг ашиглан $x$ гэсэн нийлбэр утгыг гаргаж чадаж байх юм.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $k$ ($1  ≤  n, k  ≤  500$) өгөгдөх ба эдгээр нь харгалзан зооснуудын тоо болох шоколадны үнийг илэрхийлэх юм.

Дараагийн мөрөнд бүхэл тоонууд $c_{1}, c_{2}, ..., c_{n}$ ($1 ≤ c_{i} ≤ 500$) өгөгдөх ба эдгээр нь Пари-д байгаа зооснуудын үнийг илэрхийлнэ.

Түүнчлэн эдгээр зооснуудыг ашиглан $k$ гэсэн утгыг гаргаж чадах юм. Өөрөөр хэлбэл ямар ч тохиолдолд шоколадыг худалдан авах зам байна гэсэн үг юм.

Гаралт

Гаралтын эхний мөрөнд ганц бүхэл тоо $q$-г хэвлэх ба энэ нь бүх боломжит $x$-ын утгуудын тоог илэрхийлнэ. Дараа нь $q$ ширхэг бүхэл тоонуудыг өсөх дарааллаар хэвлэх ба эдгээр нь Пари-ын шоколад худалдан авах гэж төлсөн зооснуудыг ашиглан Аря-ын гаргаж чадах утгуудыг илэрхийлэх юм.

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

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

Оролт
6 18
5 6 1 10 12 2
Гаралт
16
0 1 2 3 5 6 7 8 10 11 12 13 15 16 17 18 
Оролт
3 50
25 25 50
Гаралт
3
0 25 50 
Сэтгэгдлүүдийг ачааллаж байна...