B.Bitin çevrilməsi

Sizə qeyri-mənfi tam ədədi ifadə edən, uzunluğu $n$ olan ikilik sətir $S$ verilir. Sətrin hər simvolu 0 və ya 1-dir. Həmçinin $C=[c_1,c_2,\ldots,c_n]$ tam ədədlər massivi verilir. $c_i$, $i$-ci biti çevirməyin (0-ı 1-ə və ya 1-i 0-a dəyişməyin) qiymətidir. Sizin ümumi $K$ büdcəniz var.

İstənilən sayda biti, o cümlədən heç bir biti çevirməməyi seçə bilərsiniz. Aşağıdakı şərtlər ödənilməlidir:

• Çevrilən bütün bitlərin qiymətlərinin cəmi $K$-dan çox olmamalıdır.
• Alınan ikilik sətir tək ədədi ifadə etməlidir. Başqa sözlə, son simvol 1 olmalıdır.

Bu şərtləri ödəyən ən kiçik mümkün ədədi tapın. Alınan ikilik sətri 2-lik say sistemindəki ədəd kimi şərh edin və nəticəni onluq say sistemində çap edin. Büdcə daxilində tək ədəd almaq mümkün deyilsə, -1 çap edin.

Giriş verilənləri

• Birinci sətirdə ikilik sətrin uzunluğu və ümumi büdcə olan $n$ və $K$ ($1\le n\le 60$, $0\le K\le 10^{15}$) tam ədədləri verilir.
• İkinci sətirdə uzunluğu $n$ olan $S$ ikilik sətri verilir.
• Üçüncü sətirdə $n$ tam ədəd $c_1,c_2,\ldots,c_n$ ($0\le c_i\le 10^9$) verilir. $c_i$, $i$-ci biti çevirməyin qiymətidir.

Bitlər soldan sağa, $1$-dən başlayaraq nömrələnir. Buna görə də $c_n$ sonuncu (ən kiçik mərtəbəli) bitin çevrilmə qiymətidir.

Çıxış verilənləri

Büdcə daxilində əldə edilə bilən ən kiçik tək ədədi çap edin. Belə ədəd almaq mümkün deyilsə, -1 çap edin.

İzah

İlkin sətir $10110_2=22$ ədədini ifadə edir. Birinci biti (qiyməti $3$), üçüncü biti (qiyməti $1$) və sonuncu biti (qiyməti $2$) çevirək. Ümumi xərc $3+1+2=6\le 7$ olur. Nəticədə 00011 sətri alınır və bu, $3$ ədədinə bərabərdir. Bu giriş üçün əldə edilə bilən ən kiçik tək ədəd $3$-dür.

Məhdudiyyətlər və qiymətləndirmə

Maksimum bal 100-dür.

• Alt tapşırıq 1 — 20 bal: $1\le n\le 20$, $0\le K\le 1000$.
• Alt tapşırıq 2 — 30 bal: $1\le n\le 40$, $0\le K\le 10^9$.
• Alt tapşırıq 3 — 50 bal: Əlavə məhdudiyyət yoxdur.

Alt tapşırıqlar ayrıca yoxlanılır. Alt tapşırığın ballarını qazanmaq üçün həmin alt tapşırığa aid bütün testlərdən uğurla keçmək lazımdır.

5 7
10110
3 2 1 4 2

3