Masala D

Gavhar kiyim do’konidan so’ng sonlar do’konini ham ochdi. Do’konda $i$-sonning qiymati $a[i]$ ga teng va narxi $c[i]$ so’m turadi.

Umidning sevimli soni $T$ga teng. Umid do’kondan bir-nechta sonlarni sotib olmoqchi, bunda ularning ko’paytmasi $T$ga teng bo’lishi, umumiy narxi esa minimal bo’lishi zarur. Umidga yordam bering.

Birinchi qatorda sizga $N$ va $T$ sonlari beriladi.

Ikkinchi qatorda $a[1], a[2], ..., a[N]$ - sonlarning qiymati.

Uchinchi qatorda $c[1], c[2], ..., c[N]$ - sonlarning narxi.

Chegaralar

• $1 ≤ N ≤ 10^5$
• $2 ≤ T ≤ 10^9$
• $1 ≤ a[i] ≤ 10^9$ , barcha $1 ≤ i ≤ N$ uchun
• $1 ≤ c[i] ≤ 10^9$ , barcha $1 ≤ i ≤ N$ uchun

Subtasks

1. (12 ball) $N ≤ 18$
2. (13 ball) $N ≤ 100$, $T ≤ 100$
3. (20 ball) $N ≤ 1000$, $T ≤ 1000$.
4. (11 ball) $T = 2^x$ , bunda $x$ - musbat butun son.
5. (29 ball) $C[i] = 1$, barcha $1 ≤ i ≤ N$ uchun
6. (15 ball) Qo’shimcha chegaralarsiz

Shuningdek, har bir subtaskda, agar minimal narxni topib, aynan qaysi sonlarni sotib olish kerakligini chiqarmasangiz, shu subtask ballarini 70% miqdorini qo’lga kiritasiz. Bunda javobda $k = 0$ chiqarishingiz kerak, ya’ni:
 $C \space 0$

Agar ko’paytmani $T$ga tenglashtirishning iloji yo’q bo’lsa, yagona qatorda $−1$ chiqaring. Aks holda:

Birinchi qatorda $C$ - minimal narx, $k$ - tanlangan elementlar soni.

Ikkinchi qatorda $b[1], b[2], ..., b[k]$ - tanlangan sonlar indekslari.

Bunda $1 ≤ b[1] < b[2] < ... < b[k] ≤ N$ bo’lishi, $a[b[1]] \times ... \times a[b[k]] = T$ va $c[b[1]] + ... + c[b[k]] = C$ bo’lishi talab e’tiladi.

Agar minimal narxda sotib olish variantlari ko’p bo’lsa, ulardan ixtiyoriysini chiqarishingiz mumkin.