Bài toán đổi tiền

Submit solution
Points: 3
Time limit: 1.0s
Memory limit: 98M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Ngân hàng có \(n\) mệnh giá tiền có số lượng mỗi tờ tiền là vô hạn gồm \(a_1,a_2,...a_n\). Một người muốn đổi số tiền \(M\) theo các mệnh giá tiền này hãy tìm cách đổi sao cho số tờ tiền là ít nhất

Input

Dòng đầu chứa hai số \(n (1 \le n \le 100)\) là số loại mệnh giá ngân hàng có và số truy vấn \(q (1\le q \le 1000)\)

Dòng tiếp theo chứa n số nguyên dương không vượt quá \(10^4\) đôi một khác nhau là các loại mệnh giá tiền mà ngân hàng có

Cuối cùng gồm \(q\) dòng mỗi dòng một giá trị \(M (1 \le M \le 10^4)\) và số tiền muốn đổi

Ouput

Gồm \(q\) dòng mỗi dòng một số nguyên dương là số tờ tiền ít nhất đổi được, trong trường hộp không đổi được tiền thì xuất \(-1\)

Ví dụ 1

Input

3 2
1 7 5
10
18

Ouput

2
4

Giải thích : Đổi 10 gồm 2 tờ có mệnh giá 5 còn 18 thì có 4 tờ gồm \(5+5+7+1\)

Ví dụ 2

Input

3 2
15 6 8
11
12

Ouput

-1
2
tichpx

Comments