C. Массив хадгалах санах ой

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

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

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

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

Та ажиллахаар компьютерээ асаасан. Та код бичиж эхэлсэн ба бүхэл процессд шуурхай санах ойд зориулж жижиг бодлого өгсөн. Энэ бодлого дээр таны хийх ажил бол таны компьютерийн ажиллаж болохуйц кодонд тааралдсан асуудлуудаас нэгийг нь шийдэх юм.

Бид шуурхай санах ойг өгөгдөл хадгалдаг үүрүүдийн дараалал гэж үзнэ. Зарим үүрүүд өгөгдөлтэй байгаа бол зарим нь хоосон. Хоосон үүрүүд санах ойн багцыг бүрдүүлдэг. Санах ойн багц бол хэд хэдэн дараалласан хоосон санах ойн үүрүүдийн дараалал юм.

Танд яг $n$ ширхэг санах ойн багц байгаа ба $i$-р багц нь $a_{i}$ үүрнээс тогтоно. Та өөрийн програмд байгаа $m$ массивуудыг хадгалах санах ой олох хэрэгтэй. $j$-р массив санах ойд $2^{b_{j}}$ дараалласан санах ойн үүр эзлэнэ. Энд бүх $m$ массивуудыг багтаах санах ой байхгүй бөгөөд таны ажил бол хоосон байгаа санах ойн багцуудад байрлаж багтах массивуудын хамгийн их тоог олох юм. Мэдээж массивууд санах ойн багцуудад хуваагдаж чадахгүй. Мөн ямар ч үүр хоёр массивт хамаарагдаж болохгүй.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ($1 ≤ n, m ≤ 10^{6}$) байна. Дараагийн мөрөнд $n$ бүхэл тоон утгууд $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 10^{9}$) байна. Дараагийн мөрөнд $m$ бүхэл тоон утгууд $b_{1}, b_{2}, ..., b_{m}$ ($1 ≤ 2^{b_{i}} ≤ 10^{9}$) байна.

Гаралт

Бодлогын хариу болох бүхэл тоон утгыг хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
5 3
8 4 3 2 2
3 2 2
Гаралт
2
Оролт
10 6
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0
Гаралт
6

Тэмдэглэл

Эхний жишээн дээр танд 8, 4, 3, 2, 2 хэмжээтэй санах ойн багцууд өгөгдсөн ба 8, 4, 4 хэмжээтэй массивууд өгөгдсөн. Хариуг 2 гаргах хэд хэдэн зам байна: та 8 хэмжээтэй массивыг 8 хэмжээтэй багцад байрлуулах ба 4 хэмжээтэй хоёр массивын аль нэгийг нь 4 хэмжээтэй багцад байрлуулж болно. Өөр нэг зам бол 4 хэмжээтэй 2 массивыг 8 хэмжээтэй багцад байрлуулах юм.

Хоёр дахь жишээн дээр танд 1 хэмжээтэй 10 санах ойн багц өгөгдсөн ба 1 хэмжээтэй 6 массив өгөгдсөн. Та дурын 6 багцаа сонгоод өгөгдсөн бүх массивыг байрлуулах боломжтой.

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