题面：

D. Coins and Queries

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 $an{s}_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

Copy

5 42 4 8 2 4851410

output

Copy

1-132

题目描述：

    给你n个硬币，每个硬币的面值都为2的幂次方。先有q个询问，每个询问给出一个数b，问你至少用多少个硬币才能使得他们的面值凑成b。若不能凑出，则输出-1。

题目分析：

    因为题目中所给的硬币的面值都是2的倍数，因此，若我们要使得用最少的硬币凑出一个数，我们则应该贪心的从最大的2的倍数进行枚举，优先选取大的硬币，并将该数除以该面值。而若将这个过程做完后还不能使得原来的数为0，则输出-1。

代码：

#include 
    
     using namespace std;map
     
      mp;//用map来存储硬币的面额int main(){    int n,q;    cin>>n>>q;    for(int i=0;i
      
       =1;i>>=1){            if(mp.count(i)==0) continue;//如果不存在i的面额            else{                int x=min(mp[i],num/i);//取面额i和num/i中的最小值                num-=x*i;                ans+=x;            }        }        if(num){            puts("-1");            continue;        }        else cout<
       
        <