Problem Statement
Xiko gives you a sequence $a$ of length $n$ and an array $w$.
For a constant $L$, define $f(x)$ as the set generated by the following operations:
- Insert $x$ into the set.
- Update $x \leftarrow x + w_{\mathrm{popcount}(x)}$, where $\mathrm{popcount}(x)$ denotes the number of $1$ bits in the binary representation of $x$. If $x > L$, stop; otherwise, go back to step 1.
Xiko wants to know the size of $\bigcup_{i=1}^n f(a_i)$. Can you help him?
Input Format
The first line contains two positive integers $n, L$.
The second line contains an array $w$ of length $62$.
The third line contains an array $a$ of length $n$.
Output Format
Output a single integer, the answer.
Example
Input #1
3 246 7 2 1 10 3 9 4 8 5 6 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 97 112 72
Output #1
42
Notes
For all data: $n \le 6 \times 10^4$, $1 \le w_i \le 62$, $1 \le a_i \le L$.
Scoring
| Subtask | Points | $n \le$ | $L \le$ | Special Property |
|---|---|---|---|---|
| $1$ | $3$ | $10^3$ | $10^4$ | A |
| $2$ | $5$ | $6\times 10^4$ | $2^{30}-1$ | |
| $3$ | $10$ | $1$ | $2^{60}-1$ | None |
| $4$ | $12$ | $10$ | ||
| $5$ | $15$ | $10^2$ | ||
| $6$ | $24$ | $3\times 10^4$ | A | |
| $7$ | $31$ | $6\times 10^4$ | None |
- Special Property A: $w_i = i$, and $a_i$ are uniformly random in $[1, L]$.