eolymp
bolt
Try our new interface for solving problems
Məsələlər

Упаковка воды

Упаковка воды

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 16 MiB

Шло время, изина вода становилась всё известнее и популярнее, пока, наконец, Изя не стал основным поставщиком воды в стране. Все крупные корпорации, заведения, просто коллективы считали своим долгом покупать воду только у Изи. И, когда дело достигло таких масштабов, появились новые проблемы.

Заказы стали приходить на очень большое количество воды. Такое, что не уместится ни в одну бутылку. Поэтому Изя нанял фургон, на котором воду можно доставлять в любых количествах. Теперь оставался только один вопрос – как отмерить необходимый объём?

К счастью, у Изи оказалось целых N видов бутылок, каждая из которых была рассчитана на определённый объём воды. Теперь оказалось необходимо для каждого заказа наиболее компактно разлить соответствующее количество воды по бутылям.

Giriş verilənləri

В первой строке содержится одно число N (2N10) – количество видов бутылок, которые есть у Изи.

Во второй строке через пробел задано N натуральных чисел a_i_{ }(1a_i1000)– объём, помещающийся в i-ю бутылку. Следует отметить, что разные виды бутылок не обязательно различаются по объёму. Количество бутылок каждого вида неограниченно.

В третьей строке содержится одно число M (1M100000) – количество заказов, поступивших Изе.

В каждой из M следующих строк содержится одно число X_j_{ }(1X_j10^14) – требуемый объём воды для j-го заказа.

Çıxış verilənləri

Для каждого из M заказов в отдельной строке выведите минимальное число бутылок, в которые можно разлить ровно X_j воды. Если же не существует такого набора бутылок, выведите -1.

Nümunə

Giriş verilənləri #1
2
2 3
7
1
2
3
4
5
6
7
Çıxış verilənləri #1
-1
1
1
2
2
2
3
Müəllif Александр Винц