Polycarp has $n$ coins, the value of the $i$-th coin is $a_i$. It is guaranteed that all the values are integer powers of $2$ (i.e. $a_i = 2^d$ for some non-negative integer number $d$).

Polycarp wants to know answers on $q$ queries. The $j$-th query is described as integer number $b_j$. The answer to the query is the minimum number of coins that is necessary to obtain the value $b_j$ using some subset of coins (Polycarp can use only coins he has). If Polycarp can't obtain the value $b_j$, the answer to the $j$-th query is -1.

The queries are independent (the answer on the query doesn't affect Polycarp's coins).


-----Input-----

The first line of the input contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the number of coins and the number of queries.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ — values of coins ($1 \le a_i \le 2 \cdot 10^9$). It is guaranteed that all $a_i$ are integer powers of $2$ (i.e. $a_i = 2^d$ for some non-negative integer number $d$).

The next $q$ lines contain one integer each. The $j$-th line contains one integer $b_j$ — the value of the $j$-th query ($1 \le b_j \le 10^9$).


-----Output-----

Print $q$ integers $ans_j$. The $j$-th integer must be equal to the answer on the $j$-th query. If Polycarp can't obtain the value $b_j$ the answer to the $j$-th query is -1.


-----Example-----
Input
5 4
2 4 8 2 4
8
5
14
10

Output
1
-1
3
2
[{"code": "from collections import Counter\n\nn, q = map(int, input().split())\na = map(int, input().split())\nb = [int(input()) for _ in range(q)]\n\ncounts = 32 * [0]\n\nfor value, count in Counter(a).items():\n    counts[value.bit_length() - 1] = count\n\nfor bj in b:\n    ans = 0\n    \n    for i in reversed(range(32)):\n        count = min(bj >> i, counts[i])\n        ans += count\n        bj -= count << i\n    \n    if bj != 0:\n        print(-1)\n    else:\n        print(ans)", "passed": true, "time": 0.14, "memory": 14244.0, "status": "done"}, {"code": "#!/usr/bin/env python3\n# -*- coding: utf-8 -*-\n\"\"\"\nhttp://codeforces.com/contest/1003/problem/D\n\"\"\"\n\nfrom typing import List\nfrom collections import defaultdict\nfrom sys import stdin, stdout\n\n\ndef binarySearch(arr: List, low: int, high: int, val: int):\n\tans = 0\n\twhile low <= high:\n\t\tmid = (low + high) // 2\n\t\tif arr[mid] > val:\n\t\t\thigh = mid - 1\n\t\telif arr[mid] == val:\n\t\t\treturn mid\n\t\telse:  #2**mid<val:\n\t\t\tans = mid\n\t\t\tlow = mid + 1\n\treturn ans\n\n\nN, Q = list(map(int, stdin.readline().split()))\ncoins = sorted(list(map(int, stdin.readline().split())))\n\nfreq = defaultdict(int)\nfor word in coins:\n\tfreq[word] += 1\n\ncoins = sorted(list(freq.keys()))\n\nfor _ in range(Q):\n\tnum = int(stdin.readline())\n\tindex = binarySearch(coins, 0, len(coins) - 1, num)\n\tans = 0\n\twhile index >= 0 and num > 0:\n\t\tused = num // coins[index]\n\t\tif used >= freq[coins[index]]:\n\t\t\tused = freq[coins[index]]\n\t\tnum -= coins[index] * used\n\t\tans += used\n\t\tindex -= 1\n\tif num == 0:\n\t\tstdout.write(str(ans))\n\telse:\n\t\tstdout.write('-1')\n\tstdout.write('\\n')\n\"\"\"\n/***\n\n5 4\n2 4 8 2 4\n8\n5\n14\n10\n---\n1\n-1\n3\n2\n\n5 5\n2 4 8 2 1073741824\n8\n5\n14\n10\n1073741824\n---\n1\n-1\n3\n2\n1\n\n***/\n\"\"\"", "passed": true, "time": 0.17, "memory": 15304.0, "status": "done"}, {"code": "from collections import Counter\nn,q=map(int, input().split())\na=map(int, input().split())\nb=[int(input()) for _ in range(q)]\ncounts=32 * [0]\nfor value, count in Counter(a).items():\n    counts[value.bit_length() - 1] = count\nfor bj in b:\n    ans = 0\n    for i in reversed(range(32)):\n        count=min(bj >> i, counts[i])\n        ans+=count\n        bj-=count << i\n    if bj!=0:\n        print(-1)\n    else:\n        print(ans)", "passed": true, "time": 0.14, "memory": 14060.0, "status": "done"}, {"code": "from collections import Counter\nn,q=map(int, input().split())\na=map(int, input().split())\nb=[int(input()) for _ in range(q)]\ncounts=32 * [0]\nfor value, count in Counter(a).items():\n    counts[value.bit_length() - 1] = count\nfor bj in b:\n    ans = 0\n    for i in reversed(range(32)):\n        count=min(bj >> i, counts[i])\n        ans+=count\n        bj-=count << i\n    if bj!=0:\n        print(-1)\n    else:\n        print(ans)", "passed": true, "time": 0.15, "memory": 14360.0, "status": "done"}, {"code": "#!/usr/bin/env python3\n# encoding: utf-8\n\nfrom collections import Counter\n\nn, q = list(map(int, input().split()))\na = list(map(int, input().split()))\nb = [int(input()) for _ in range(q)]\n\ncounts = 32 * [0]\n\nfor value, count in list(Counter(a).items()):\n    counts[value.bit_length() - 1] = count\n\nfor bj in b:\n    ans = 0\n\n    for i in reversed(list(range(32))):\n        count = min(bj >> i, counts[i])\n        ans += count\n        bj -= count << i\n\n    if bj != 0:\n        print(-1)\n    else:\n        print(ans)\n", "passed": true, "time": 0.24, "memory": 14384.0, "status": "done"}, {"code": "#!/usr/bin/env python3\n# encoding: utf-8\n\n\n\n#----------\n# Constants\n#----------\n\nDEGREE_ARRAY_SIZE = 32\nb = [ 0 for i in range(DEGREE_ARRAY_SIZE) ]\n\n#----------\n# Functions\n#----------\ndef convert(a):\n    from collections import Counter\n    #b = [ 0 for i in range(DEGREE_ARRAY_SIZE) ]\n    for val, cnt in list(Counter(a).items()):\n        b[val.bit_length()-1] += cnt\n    start = 0\n    for i, cnt in enumerate(reversed(b)):\n        if cnt != 0:\n            start = DEGREE_ARRAY_SIZE - i\n            break\n    return b, start\n\n\ndef calc(q):\n    ans = 0\n    val_power = (len(b) - 1)\n    for cnt in reversed(b):\n        c = min(cnt, q >> val_power)\n        q -= c * (1 << val_power)\n        ans += c\n        #if q == 0:\n        #    break\n        val_power -= 1\n\n    return ans if q == 0 else -1\n\n\n# Reads a string from stdin, splits it by space chars, converts each\n# substring to int, adds it to a list and returns the list as a result.\ndef get_ints():\n    return [ int(n) for n in input().split() ]\n\n\n# Reads a string from stdin, splits it by space chars, converts each substring\n# to floating point number, adds it to a list and returns the list as a result.\ndef get_floats():\n    return [ float(n) for n in input().split() ]\n\n\n#----------\n# Execution start point\n#----------\n\ndef __starting_point():\n    a = get_ints()\n    assert len(a) == 2\n    n, q = a[0], a[1]\n    a = get_ints()\n    assert len(a) == n\n\n    b, start = convert(a)\n#    print(str(b))\n#    print(total)\n    b = b[:start]\n    DEGREE_ARRAY_SIZE = start\n#    print(str(b))\n\n    q = [int(input()) for _ in range(q)]\n    for i in q:\n        ans = calc(i)\n        print(ans)\n\n__starting_point()", "passed": true, "time": 0.14, "memory": 14340.0, "status": "done"}, {"code": "#!/usr/bin/env python3\n# encoding: utf-8\n\n\n\n#----------\n# Constants\n#----------\n\nDEGREE_ARRAY_SIZE = 32\n\n#----------\n# Functions\n#----------\ndef convert(a):\n    from collections import Counter\n    b = [ 0 for i in range(DEGREE_ARRAY_SIZE) ]\n    for val, cnt in list(Counter(a).items()):\n        b[val.bit_length()-1] += cnt\n    start = 0\n    for i, cnt in enumerate(reversed(b)):\n        if cnt != 0:\n            start = DEGREE_ARRAY_SIZE - i\n            break\n    return b, start\n\n\ndef calc(q, b):\n    ans = 0\n    val_power = (len(b) - 1)\n    for cnt in reversed(b):\n        c = min(cnt, q >> val_power)\n        q -= c * (1 << val_power)\n        ans += c\n        #if q == 0:\n        #    break\n        val_power -= 1\n\n    return ans if q == 0 else -1\n\n\n# Reads a string from stdin, splits it by space chars, converts each\n# substring to int, adds it to a list and returns the list as a result.\ndef get_ints():\n    return [ int(n) for n in input().split() ]\n\n\n# Reads a string from stdin, splits it by space chars, converts each substring\n# to floating point number, adds it to a list and returns the list as a result.\ndef get_floats():\n    return [ float(n) for n in input().split() ]\n\n\n#----------\n# Execution start point\n#----------\n\ndef __starting_point():\n    a = get_ints()\n    assert len(a) == 2\n    n, q = a[0], a[1]\n    a = get_ints()\n    assert len(a) == n\n\n    b, start = convert(a)\n#    print(str(b))\n#    print(total)\n    b = b[:start]\n    DEGREE_ARRAY_SIZE = start\n#    print(str(b))\n\n    q = [int(input()) for _ in range(q)]\n    for i in q:\n        ans = calc(i, b)\n        print(ans)\n\n__starting_point()", "passed": true, "time": 0.14, "memory": 14192.0, "status": "done"}, {"code": "#!/usr/bin/env python3\n# encoding: utf-8\n\n\n\n#----------\n# Constants\n#----------\n\nDEGREE_ARRAY_SIZE = 32\n\n#----------\n# Functions\n#----------\ndef convert(a):\n    from collections import Counter\n    b = [ 0 for i in range(DEGREE_ARRAY_SIZE) ]\n    for val, cnt in list(Counter(a).items()):\n        b[val.bit_length()-1] += cnt\n    start = 0\n    for i, cnt in enumerate(reversed(b)):\n        if cnt != 0:\n            start = DEGREE_ARRAY_SIZE - i\n            break\n    return b, start\n\n\ndef calc(q, b):\n    ans = 0\n    val_power = (len(b) - 1)\n    for cnt in reversed(b):\n        c = min(cnt, q >> val_power)\n        q -= c * (1 << val_power)\n        ans += c\n        if q == 0:\n            break\n        val_power -= 1\n\n    return ans if q == 0 else -1\n\n\n# Reads a string from stdin, splits it by space chars, converts each\n# substring to int, adds it to a list and returns the list as a result.\ndef get_ints():\n    return [ int(n) for n in input().split() ]\n\n\n# Reads a string from stdin, splits it by space chars, converts each substring\n# to floating point number, adds it to a list and returns the list as a result.\ndef get_floats():\n    return [ float(n) for n in input().split() ]\n\n\n#----------\n# Execution start point\n#----------\n\ndef __starting_point():\n    a = get_ints()\n    assert len(a) == 2\n    n, q = a[0], a[1]\n    a = get_ints()\n    assert len(a) == n\n\n    b, start = convert(a)\n#    print(str(b))\n#    print(total)\n    b = b[:start]\n    DEGREE_ARRAY_SIZE = start\n#    print(str(b))\n\n    q = [int(input()) for _ in range(q)]\n    for i in q:\n        ans = calc(i, b)\n        print(ans)\n\n__starting_point()", "passed": true, "time": 0.14, "memory": 14216.0, "status": "done"}, {"code": "#!/usr/bin/env python3\n# encoding: utf-8\n\n\n\n#----------\n# Constants\n#----------\n\nDEGREE_ARRAY_SIZE = 32\n\n#----------\n# Functions\n#----------\ndef convert(a):\n    from collections import Counter\n    b = [ 0 for i in range(DEGREE_ARRAY_SIZE) ]\n    for val, cnt in list(Counter(a).items()):\n        b[val.bit_length()-1] += cnt\n    start = 0\n    for i, cnt in enumerate(reversed(b)):\n        if cnt != 0:\n            start = DEGREE_ARRAY_SIZE - i\n            break\n    return b, start\n\n\ndef calc(q, b):\n    ans = 0\n    val = 2 ** (len(b) - 1)\n    for cnt in reversed(b):\n        c = min(cnt, q // val)\n        q -= c * val\n        ans += c\n        if q == 0:\n            break\n        val //= 2\n\n    return ans if q == 0 else -1\n\n\n# Reads a string from stdin, splits it by space chars, converts each\n# substring to int, adds it to a list and returns the list as a result.\ndef get_ints():\n    return [ int(n) for n in input().split() ]\n\n\n# Reads a string from stdin, splits it by space chars, converts each substring\n# to floating point number, adds it to a list and returns the list as a result.\ndef get_floats():\n    return [ float(n) for n in input().split() ]\n\n\n#----------\n# Execution start point\n#----------\n\ndef __starting_point():\n    a = get_ints()\n    assert len(a) == 2\n    n, q = a[0], a[1]\n    a = get_ints()\n    assert len(a) == n\n    qj = [int(input()) for i in range(q)]\n    assert len(qj) == q\n\n    b, start = convert(a)\n#    print(str(b))\n#    print(total)\n    b = b[:start]\n    DEGREE_ARRAY_SIZE = start\n#    print(str(b))\n\n    for i in qj:\n        ans = calc(i, b)\n        print(ans)\n\n__starting_point()", "passed": true, "time": 0.15, "memory": 14408.0, "status": "done"}, {"code": "#!/usr/bin/env python3\n# encoding: utf-8\n\n\n\n#----------\n# Constants\n#----------\n\nDEGREE_ARRAY_SIZE = 32\nVALUES = { 2**i: i for i in range(DEGREE_ARRAY_SIZE) }\n\n#----------\n# Functions\n#----------\ndef convert(a):\n    from collections import Counter\n    b = [ 0 for i in range(DEGREE_ARRAY_SIZE) ]\n    for val, cnt in list(Counter(a).items()):\n        b[VALUES[val]] += cnt\n    start = 0\n    for i, cnt in enumerate(reversed(b)):\n        if cnt != 0:\n            start = DEGREE_ARRAY_SIZE - i\n            break\n    return b, start\n\n\ndef calc(q, b):\n    ans = 0\n    val = 2 ** (len(b) - 1)\n    for cnt in reversed(b):\n        c = min(cnt, q // val)\n        q -= c * val\n        ans += c\n        if q == 0:\n            break\n        val //= 2\n\n    return ans if q == 0 else -1\n\n\n# Reads a string from stdin, splits it by space chars, converts each\n# substring to int, adds it to a list and returns the list as a result.\ndef get_ints():\n    return [ int(n) for n in input().split() ]\n\n\n# Reads a string from stdin, splits it by space chars, converts each substring\n# to floating point number, adds it to a list and returns the list as a result.\ndef get_floats():\n    return [ float(n) for n in input().split() ]\n\n\n#----------\n# Execution start point\n#----------\n\ndef __starting_point():\n    a = get_ints()\n    assert len(a) == 2\n    n, q = a[0], a[1]\n    a = get_ints()\n    assert len(a) == n\n    qj = [int(input()) for i in range(q)]\n    assert len(qj) == q\n\n    b, start = convert(a)\n#    print(str(b))\n#    print(total)\n    b = b[:start]\n    DEGREE_ARRAY_SIZE = start\n#    print(str(b))\n\n    for i in qj:\n        ans = calc(i, b)\n        print(ans)\n\n__starting_point()", "passed": true, "time": 0.15, "memory": 14320.0, "status": "done"}, {"code": "#!/usr/bin/env python3\n# encoding: utf-8\n\n\n\n#----------\n# Constants\n#----------\n\nDEGREE_ARRAY_SIZE = 32\nVALUES = { 2**i: i for i in range(DEGREE_ARRAY_SIZE) }\n\n#----------\n# Functions\n#----------\ndef convert(a):\n    from collections import Counter\n    b = [ 0 for i in range(DEGREE_ARRAY_SIZE) ]\n    total = 0\n    for val, cnt in list(Counter(a).items()):\n        b[VALUES[val]] += cnt\n        total += cnt * val\n    start = 0\n    for i, cnt in enumerate(reversed(b)):\n        if cnt != 0:\n            start = DEGREE_ARRAY_SIZE - i\n            break\n    return b, total, start\n\n\ndef calc(q, b):\n    ans = 0\n    val = 2 ** (len(b) - 1)\n    for cnt in reversed(b):\n        c = min(cnt, q // val)\n        q -= c * val\n        ans += c\n        if q == 0:\n            break\n        val //= 2\n\n    return ans if q == 0 else -1\n\n\n# Reads a string from stdin, splits it by space chars, converts each\n# substring to int, adds it to a list and returns the list as a result.\ndef get_ints():\n    return [ int(n) for n in input().split() ]\n\n\n# Reads a string from stdin, splits it by space chars, converts each substring\n# to floating point number, adds it to a list and returns the list as a result.\ndef get_floats():\n    return [ float(n) for n in input().split() ]\n\n\n#----------\n# Execution start point\n#----------\n\ndef __starting_point():\n    a = get_ints()\n    assert len(a) == 2\n    n, q = a[0], a[1]\n    a = get_ints()\n    assert len(a) == n\n    qj = [int(input()) for i in range(q)]\n    assert len(qj) == q\n\n    b, total, start = convert(a)\n    b = b[:start]\n    assert sum(b) == n\n\n    DEGREE_ARRAY_SIZE = start\n\n    for i in qj:\n        if i < total:\n            ans = calc(i, b)\n        elif i == total:\n            ans = n\n        else:\n            ans = -1\n        print(ans)\n\n__starting_point()", "passed": true, "time": 0.14, "memory": 14228.0, "status": "done"}, {"code": "#!/usr/bin/env python3\n# encoding: utf-8\n\n\n\n#----------\n# Constants\n#----------\n\nDEGREE_ARRAY_SIZE = 32\nVALUES = { 2**i: i for i in range(DEGREE_ARRAY_SIZE) }\n\n#----------\n# Functions\n#----------\ndef convert(a):\n    from collections import Counter\n    b = [ 0 for i in range(DEGREE_ARRAY_SIZE) ]\n    total = 0\n    for val, cnt in list(Counter(a).items()):\n        b[VALUES[val]] += cnt\n        total += cnt * val\n    start = 0\n    for i, cnt in enumerate(reversed(b)):\n        if cnt != 0:\n            start = DEGREE_ARRAY_SIZE - i\n            break\n    return b, total, start\n\n\ndef calc(q, b):\n    ans = 0\n    val = 2 ** (len(b) - 1)\n    for cnt in reversed(b):\n        if q >= val:\n            c = min(cnt, q // val)\n            q -= c * val\n            ans += c\n            if q == 0:\n                break\n        val //= 2\n\n    return ans if q == 0 else -1\n\n\n# Reads a string from stdin, splits it by space chars, converts each\n# substring to int, adds it to a list and returns the list as a result.\ndef get_ints():\n    return [ int(n) for n in input().split() ]\n\n\n# Reads a string from stdin, splits it by space chars, converts each substring\n# to floating point number, adds it to a list and returns the list as a result.\ndef get_floats():\n    return [ float(n) for n in input().split() ]\n\n\n#----------\n# Execution start point\n#----------\n\ndef __starting_point():\n    a = get_ints()\n    assert len(a) == 2\n    n, q = a[0], a[1]\n    a = get_ints()\n    assert len(a) == n\n    qj = [int(input()) for i in range(q)]\n    assert len(qj) == q\n\n    b, total, start = convert(a)\n    b = b[:start]\n    assert sum(b) == n\n\n    DEGREE_ARRAY_SIZE = start\n\n    for i in qj:\n        if i < total:\n            ans = calc(i, b)\n        elif i == total:\n            ans = n\n        else:\n            ans = -1\n        print(ans)\n\n__starting_point()", "passed": true, "time": 0.24, "memory": 14384.0, "status": "done"}, {"code": "#!/usr/bin/env python3\n# encoding: utf-8\n\n\n\n#----------\n# Constants\n#----------\n\nDEGREE_ARRAY_SIZE = 32\nVALUES = { 2**i: i for i in range(DEGREE_ARRAY_SIZE) }\n\n#----------\n# Functions\n#----------\ndef convert(a):\n    from collections import Counter\n    b = [ 0 for i in range(DEGREE_ARRAY_SIZE) ]\n    total = 0\n    for val in a:\n        b[VALUES[val]] += 1\n        total += val\n    start = 0\n    for i, cnt in enumerate(reversed(b)):\n        if cnt != 0:\n            start = DEGREE_ARRAY_SIZE - i\n            break\n    return b, total, start\n\n\ndef calc(q, b):\n    ans = 0\n    val = 2 ** (len(b) - 1)\n    for cnt in reversed(b):\n        if q >= val:\n            c = min(cnt, q // val)\n            q -= c * val\n            ans += c\n            if q == 0:\n                break\n        val //= 2\n\n    return ans if q == 0 else -1\n\n\n# Reads a string from stdin, splits it by space chars, converts each\n# substring to int, adds it to a list and returns the list as a result.\ndef get_ints():\n    return [ int(n) for n in input().split() ]\n\n\n# Reads a string from stdin, splits it by space chars, converts each substring\n# to floating point number, adds it to a list and returns the list as a result.\ndef get_floats():\n    return [ float(n) for n in input().split() ]\n\n\n#----------\n# Execution start point\n#----------\n\ndef __starting_point():\n    a = get_ints()\n    assert len(a) == 2\n    n, q = a[0], a[1]\n    a = get_ints()\n    assert len(a) == n\n    qj = [int(input()) for i in range(q)]\n    assert len(qj) == q\n\n    b, total, start = convert(a)\n    b = b[:start]\n    assert sum(b) == n\n\n    DEGREE_ARRAY_SIZE = start\n\n    for i in qj:\n        if i < total:\n            ans = calc(i, b)\n        elif i == total:\n            ans = n\n        else:\n            ans = -1\n        print(ans)\n\n__starting_point()", "passed": true, "time": 0.14, "memory": 14300.0, "status": "done"}, {"code": "#!/usr/bin/env python3\n# encoding: utf-8\n\n\n\n#----------\n# Constants\n#----------\n\nDEGREE_ARRAY_SIZE = 32\nVALUES = { 2**i: i for i in range(DEGREE_ARRAY_SIZE) }\n\n#----------\n# Functions\n#----------\ndef convert(a):\n    b = [ 0 for i in range(DEGREE_ARRAY_SIZE) ]\n    total = 0\n    for val in a:\n        b[VALUES[val]] += 1\n        total += val\n    start = 0\n    for i, cnt in enumerate(reversed(b)):\n        if cnt != 0:\n            start = DEGREE_ARRAY_SIZE - i\n            break\n    return b, total, start\n\n\ndef calc(q, b):\n    ans = 0\n    val = 2 ** (len(b) - 1)\n    for cnt in reversed(b):\n        #if q >= val * cnt:\n        #    q -= val * cnt\n        #    ans += cnt\n        #    if q == 0:\n        #        break\n        if q >= val:\n        #    c = min(cnt, q // val)\n        #    q -= c * val\n        #    ans += c\n            r = q % val\n            d = q // val\n            if cnt < d:\n                r += (d - cnt) * val\n                d = cnt\n            q = r\n            ans += d\n            if q == 0:\n                break\n        val //= 2\n\n    return ans if q == 0 else -1\n\n\n# Reads a string from stdin, splits it by space chars, converts each\n# substring to int, adds it to a list and returns the list as a result.\ndef get_ints():\n    return [ int(n) for n in input().split() ]\n\n\n# Reads a string from stdin, splits it by space chars, converts each substring\n# to floating point number, adds it to a list and returns the list as a result.\ndef get_floats():\n    return [ float(n) for n in input().split() ]\n\n\n#----------\n# Execution start point\n#----------\n\ndef __starting_point():\n    a = get_ints()\n    assert len(a) == 2\n    n, q = a[0], a[1]\n    a = get_ints()\n    assert len(a) == n\n    qj = [int(input()) for i in range(q)]\n    assert len(qj) == q\n\n    b, total, start = convert(a)\n    b = b[:start]\n    assert sum(b) == n\n\n    DEGREE_ARRAY_SIZE = start\n\n    for i in qj:\n        if i < total:\n            ans = calc(i, b)\n        elif i == total:\n            ans = n\n        else:\n            ans = -1\n        print(ans)\n\n__starting_point()", "passed": true, "time": 0.14, "memory": 14424.0, "status": "done"}, {"code": "#!/usr/bin/env python3\n# encoding: utf-8\n\n\n\n#----------\n# Constants\n#----------\n\nDEGREE_ARRAY_SIZE = 32\nVALUES = { 2**i: i for i in range(DEGREE_ARRAY_SIZE) }\n\n#----------\n# Functions\n#----------\ndef convert(a):\n    b = [ 0 for i in range(DEGREE_ARRAY_SIZE) ]\n    total = 0\n    for val in a:\n        b[VALUES[val]] += 1\n        total += val\n    start = 0\n    for i, cnt in enumerate(reversed(b)):\n        if cnt != 0:\n            start = DEGREE_ARRAY_SIZE - i\n            break\n    return b, total, start\n\n\ndef calc(q, b):\n    ans = 0\n    val = 2 ** (len(b) - 1)\n    for cnt in reversed(b):\n        if q >= val * cnt:\n            q -= val * cnt\n            ans += cnt\n            if q == 0:\n                break\n        elif q >= val:\n        #    c = min(cnt, q // val)\n        #    q -= c * val\n        #    ans += c\n            r = q % val\n            d = q // val\n            if cnt < d:\n                r += (d - cnt) * val\n                d = cnt\n            q = r\n            ans += d\n            if q == 0:\n                break\n        val //= 2\n\n    return ans if q == 0 else -1\n\n\n# Reads a string from stdin, splits it by space chars, converts each\n# substring to int, adds it to a list and returns the list as a result.\ndef get_ints():\n    return [ int(n) for n in input().split() ]\n\n\n# Reads a string from stdin, splits it by space chars, converts each substring\n# to floating point number, adds it to a list and returns the list as a result.\ndef get_floats():\n    return [ float(n) for n in input().split() ]\n\n\n#----------\n# Execution start point\n#----------\n\ndef __starting_point():\n    a = get_ints()\n    assert len(a) == 2\n    n, q = a[0], a[1]\n    a = get_ints()\n    assert len(a) == n\n    qj = [int(input()) for i in range(q)]\n    assert len(qj) == q\n\n    b, total, start = convert(a)\n    b = b[:start]\n    assert sum(b) == n\n\n    DEGREE_ARRAY_SIZE = start\n\n    for i in qj:\n        if i < total:\n            ans = calc(i, b)\n        elif i == total:\n            ans = n\n        else:\n            ans = -1\n        print(ans)\n\n__starting_point()", "passed": true, "time": 0.14, "memory": 14196.0, "status": "done"}, {"code": "#!/usr/bin/env python3\n# encoding: utf-8\n\n\n\n#----------\n# Constants\n#----------\n\n\n\n#----------\n# Functions\n#----------\ndef convert(a):\n    b = list()\n    toAdd = a[0]\n    cnt = 1\n    for item in a[1:]:\n        if item == toAdd:\n            cnt += 1\n        else:\n            b.append((toAdd, cnt))\n            toAdd = item\n            cnt = 1\n\n    b.append((toAdd, cnt))\n    return b\n\n\ndef calc(q, b):\n    ans = 0\n    for item in b:\n        val, cnt = item\n        if q >= val:\n            r = q % val\n            d = q // val\n            if cnt < d:\n                r += (d - cnt) * val\n                d = cnt\n            q = r\n            ans += d\n            if q == 0:\n                break\n\n    return ans if q == 0 else -1\n\n\n# Reads a string from stdin, splits it by space chars, converts each\n# substring to int, adds it to a list and returns the list as a result.\ndef get_ints():\n    return [ int(n) for n in input().split() ]\n\n\n# Reads a string from stdin, splits it by space chars, converts each substring\n# to floating point number, adds it to a list and returns the list as a result.\ndef get_floats():\n    return [ float(n) for n in input().split() ]\n\n\n#----------\n# Execution start point\n#----------\n\ndef __starting_point():\n    a = get_ints()\n    assert len(a) == 2\n    n, q = a[0], a[1]\n    a = get_ints()\n    assert len(a) == n\n    qj = [int(input()) for i in range(q)]\n    assert len(qj) == q\n\n    a.sort()\n    a.reverse()\n#    print(a)\n    b = convert(a)\n#    print(b)\n\n    for i in qj:\n        ans = calc(i, b)\n        print(ans)\n\n__starting_point()", "passed": true, "time": 0.14, "memory": 14184.0, "status": "done"}, {"code": "from collections import Counter\n\nn, q = map(int, input().split())\na = map(int, input().split())\nb = [int(input()) for _ in range(q)]\n\ncounts = 32 * [0]\n\nfor value, count in Counter(a).items():\n    \n    counts[value.bit_length() - 1] = count\n\nfor bj in b:\n    ans = 0\n    for i in reversed(range(32)):\n        count = min(bj >> i, counts[i])\n        ans += count\n        bj -= count << i\n\n    if bj != 0:\n        print(-1)\n    else:\n        print(ans)", "passed": true, "time": 0.14, "memory": 14332.0, "status": "done"}, {"code": "import collections\nn, q = map(int,input().split())\ns = [int(i) for i in input().split()]\na = [int(input()) for _ in range(q)]\ndic = [0] * 32\nfor key, val in collections.Counter(s).items():\n    dic[key.bit_length()-1] = val\nfor s in a:\n    ans = 0\n    for i in range(31, -1, -1):\n        count = min(s >> i, dic[i])\n        ans += count\n        s -= count << i\n    print(ans if s==0 else -1)", "passed": true, "time": 0.14, "memory": 14092.0, "status": "done"}, {"code": "import collections\nn, q = map(int,input().split())\ns = [int(i) for i in input().split()]\na = [int(input()) for _ in range(q)]\n'''dic = [0] * 32\nfor key, val in collections.Counter(s).items():\n    dic[key.bit_length()-1] = val'''\ndic = {}\nfor i in range(32):\n    dic[i] = 0\nfor i in s:\n    dic[i.bit_length()-1] += 1\nfor s in a:\n    ans = 0\n    for i in range(31, -1, -1):\n        count = min(s >> i, dic[i])\n        ans += count\n        s -= count << i\n    print(ans if s==0 else -1)", "passed": true, "time": 0.14, "memory": 14200.0, "status": "done"}, {"code": "import collections\nn, q = map(int, input().split())\nl = list(map(int, input().split()))\na = [int(input()) for _ in range(q)]\ncount = [0]*31\nfor key, val in collections.Counter(l).items():\n    count[key.bit_length()-1] = val\nfor x in a:\n    ans = 0\n    for i in range(30, -1, -1):\n        val = min(x >> i, count[i])\n        ans += val\n        x -= (1 << i)*val\n    print(ans if x==0 else -1)", "passed": true, "time": 0.14, "memory": 14260.0, "status": "done"}, {"code": "def main():\n\td={}\n\tnums=[None]*31\n\tfor i in range(31):\n\t\tnums[i]=2**i\n\t\td[nums[i]]=0\n\n\tn,q=map(int,input().split())\n\ta=list(map(int,input().split()))\n\tfor i in range(n):\n\t\td[a[i]]+=1\n\tfor i in range(31):\n\t\tif d[nums[i]]==0:\n\t\t\tdel d[nums[i]]\n\tkeys=sorted(list(d.keys()))[::-1]\n\tleng=len(keys)\n\tans=[0]*q\n\tfor i in range(q):\n\t\tval=int(input())\n\t\tfor j in range(leng):\n\t\t\tif keys[j]<=val:\n\t\t\t\tcoin=min(d[keys[j]],val//keys[j])\n\t\t\t\tans[i]+=coin\n\t\t\t\tval-=keys[j]*coin\n\t\t\t\tif val==0:\n\t\t\t\t\tbreak\n\t\telse:\n\t\t\tans[i]=-1\n\n\tprint('\\n'.join(list(map(str,ans))))\n\nmain()", "passed": true, "time": 0.14, "memory": 14404.0, "status": "done"}]