Problema H - O Guilherme vai às compras

Este problema foi proposto no âmbito de um dos guias de introdução das ONI. No texto original podem encontrar mais informação sobre o problema assim como alguns conceitos que precisam de saber para o resolver. O artigo é o seguinte: http://oni.dcc.fc.up.pt/loop/guias/inicial/algo/.

Para surpreender a sua família no Natal, o Guilherme decidiu comprar um conjunto de presentes. Depois de fazer uma pesquisa, encontrou N presentes que lhe interessam comprar e apontou o preço de cada um. O Guilherme quer comprar o máximo número de presentes possível, mas infelizmente tem um orçamento limitado. Para saber de quanto dinheiro precisa, o Guilherme tem M orçamentos diferentes e quer saber o máximo número de presentes que consegue comprar com cada um.

O Problema

Dado o número de presentes N que o Guilherme encontrou e os preços calcular para cada quantidade de dinheiro num orçamento o número máximo de presentes que o Guilherme consegue comprar.

Input

Dois inteiros N e M numa linha, o número de presentes e o número de orçamentos. De seguida vem uma linha com N inteiros, com os preços dos presentes, seguida uma linha com M inteiros, com os orçamentos.

Output

M linhas, cada uma contendo um inteiro, sendo que a i-ésima contém o número máximo de presentes para o i-ésimo orçamento dado no input.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

1 ≤ N ≤ 100 000       Números de presentes
1 ≤ M ≤ 100 000       Números de orçamentos
1 ≤ Pi, Oi ≤ 10 000       Preço de cada presente e orçamento

Os casos de teste deste problema estão organizados em 2 grupos com restrições adicionais diferentes:

Grupo Número de Pontos Restrições adicionais
1 40 M ≤ 1000
2 60 -

Input do Exemplo 1

6 6
8 5 3 5 6 1
5 10 27 1 2 9

Output do Exemplo 1

2
3
5
1
1
3

Input do Exemplo 2

10 5
1 3 2 4 8 1 6 6 2 4
1 5 10 15 20

Output do Exemplo 2

1
3
5
6
7