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 a1,a2,...an. 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≤n≤100) là số loại mệnh giá ngân hàng có và số truy vấn q(1≤q≤1000)

Dòng tiếp theo chứa n số nguyên dương không vượt quá 104 đô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≤M≤104) 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

Copy
3 2
1 7 5
10
18

Ouput

Copy
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

Copy
3 2
15 6 8
11
12

Ouput

Copy
-1
2
tichpx

Comments