폭발물 적재

당신은 폭발물을 운송하는 계약을 맡았다. 트럭이 $n$대 있고, $i$번째 트럭의 적재 용량은 $x_i$이다.

각 트럭을 폭발물로 어떻게 채울지 계획해야 한다. 모든 트럭은 폭발물로 빈틈없이 정확히 가득 채워야 한다. 그렇지 않으면 운송 도중 폭발물이 손상될 수 있기 때문이다. 사용할 수 있는 폭발물은 크기가 서로 다른 $k$가지 종류가 있으며, $i$번째 종류의 크기는 $y_i$이다. 각 종류의 폭발물은 필요한 만큼 얼마든지 만들 수 있다. 트럭을 싣고 내리는 속도 때문에, 트럭 하나를 채우는 데 사용하는 폭발물의 개수를 최대한 줄이고 싶다.

각 트럭에 대해, 빈틈없이 정확히 채우는 데 필요한 폭발물의 최소 개수를 구하여라.

첫째 줄에 트럭의 수 $n$과 폭발물 종류의 수 $k$가 주어진다 ($1 \le n \le 1000$, $1 \le k \le 100$). 이어지는 $k$개의 줄에는 각 폭발물 종류의 크기 $y_i$가 한 줄에 하나씩 주어진다 ($1 \le y_i < 10^5$). 서로 다른 두 종류의 크기는 항상 다르다. 이어지는 $n$개의 줄에는 각 트럭의 적재 용량 $x_i$가 한 줄에 하나씩 주어진다 ($10^{10} \le x_i \le 10^{17}$).

$n$개의 줄에 걸쳐, $i$번째 줄에는 $i$번째 트럭을 빈틈없이 정확히 채우는 데 필요한 폭발물의 최소 개수 $w_i$를 출력한다. 정확히 채우는 것이 불가능하면 그 줄에 NIE를 출력한다.