Masala #TAGJXJR76O

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.