== include(page="template/taskheader" task_id="fatkins") ==
Ion s-a apucat să țină dieta Fatkins, o dietă miraculoasă bazată pe bomboane. În fiecare zi timp de $Q$ zile, Ion primește la ușă câte o cutie cu bomboane. În fiecare cutie se află $N$ bomboane și fiecare bomboană este etichetată cu numărul de calorii pe care îl conține. Toate cutiile conțin același set de bomboane. Dar Ion nu are voie să mănânce toate bomboanele! În ziua [$i$], Ion primește un număr $K_i$. Considerând toate cele $2[^N^]$ submulțimi de bomboane, ordonate după conținutul caloric, Ion trebuie să mănânce submulțimea cu numărul de ordine $K[~i~]$.
Ion s-a apucat să țină dieta Fatkins, o dietă miraculoasă bazată pe bomboane. În fiecare zi timp de $Q$ zile, Ion primește la ușă câte o cutie cu bomboane. În fiecare cutie se află $N$ bomboane și fiecare bomboană este etichetată cu numărul de calorii pe care îl conține. Toate cutiile conțin același set de bomboane. Dar Ion nu are voie să mănânce toate bomboanele! În ziua [$i$], Ion primește un număr $K[~i~]$. Considerând toate cele $2[^N^]$ submulțimi de bomboane, ordonate după conținutul caloric, Ion trebuie să mănânce submulțimea cu numărul de ordine $K[~i~]$.
Dându-se [$N$], [$Q$], conținutul caloric al celor $N$ bomboane și valorile pentru $K[~i~]$, determinați câte calorii mănâncă Ion în fiecare zi.
h2. Date de intrare
Fișierul de intrare $fatkins.in$ conține pe prima linie numerele $N$ și [$Q$]. Pe a doua linie apar numerele întregi $C[~1~], C[~2~], ..., C[~N~]$, reprezentând numărul de calorii din fiecare bomboană. Pe următoarele $Q$ linii apar numerele întregi $K[~1~], K[~2~], ..., K[~Q~]$, câte unul pe linie.
Fișierul de intrare $fatkins.in$ conține
* pe prima linie numerele $N$ și [$Q$];
* pe a doua linie apar numerele naturale pozitive $C[~1~], C[~2~], ..., C[~N~]$, reprezentând numărul de calorii din fiecare bomboană;
* pe următoarele $Q$ linii numerele naturale $K[~1~], K[~2~], ..., K[~Q~]$, câte unul pe linie.
h2. Date de ieșire
În fișierul de ieșire $fatkins.out$ ...
În fișierul de ieșire $fatkins.out$ se vor tipări $Q$ numere, câte unul pe linie, reprezentând caloriile consumate de Ion în fiecare zi. Răspunsurile vor avea aceeași ordine cu întrebările.
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100$
* $1 ≤ Q ≤ 1.000$
* $1 ≤ K[~i~] ≤ min(2[^N^], 100.000)$ pentru $1 ≤ i ≤ Q$
* $1 ≤ C[~i~]$ pentru $1 ≤ i ≤ N$
* $C[~1~] + C[~2~] + ... + C[~N~] ≤ 1.000.000.000$
* Pentru 20% din teste, $1 ≤ N ≤ 16$ și $1 ≤ K[~i~] ≤ 10.000$
* Pentru alte 30% din teste, $1 ≤ N ≤ 30$ și $1 ≤ K[~i~] ≤ 20.000$
h2. Exemplu
table(example).
|_. fatkins.in |_. fatkins.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 4 3
7 2 6 4
6
1
15
| 7
0
17
|
h3. Explicație
...
Cele 16 submulțimi sunt, în ordine:
|_. număr |_. bomboane |_. total calorii |
| **1** | niciuna | **0** |
| 2 | 2 | 2 |
| 3 | 4 | 4 |
| 4 | 6 | 6 |
| 5 | 2, 4 | 6 |
| **6** | 7 | **7** |
| 7 | 2, 6 | 8 |
| 8 | 2, 7 | 9 |
| 9 | 4, 6 | 10 |
| 10 | 4, 7 | 11 |
| 11 | 2, 4, 6 | 12 |
| 12 | 2, 4, 7 | 13 |
| 13 | 6, 7 | 13 |
| 14 | 2, 6, 7 | 15 |
| **15** | 4, 6, 7 | **17** |
| 16 | 2, 4, 6, 7 | 19 |
== include(page="template/taskfooter" task_id="fatkins") ==
