710 . 小意的鯊鯊

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

apcsc apcsc-enumerate

Description

小意家裡養了很多鯊鯊，鯊鯊每天的伙食是非常驚人的，根據小意的計算，從今天算起的第 i 天鯊鯊們會需要吃掉至少 ai 公斤的食物。

市面上販售的鯊魚食品有 n 種，且由於新政策的推行，每一種的鯊魚食品的價錢都是相同的，然而，每一種鯊魚食品的份量卻大不相同，其中第 j 種的鯊魚食品包含了 xj 公斤的食物，而且由於鯊魚食品的種類太多了，寵物店店家每一天每一種食品的庫存都只有一份，而且跨日的鯊魚食品，鯊鯊們是不會吃的，所以當天沒吃完的食物不可以留到隔天。

由於經費有限，小意希望可以花最少的錢來餵飽家裡的鯊鯊們，你可以告訴小意每天最少要買幾份鯊魚食品才可以餵飽鯊鯊嗎？

Input Format

輸入的第一行有一個整數 t (1≤t≤1000) 代表測資的數量。

每一筆測資的第一行有兩個整數 n,q(1≤n,q≤1.5×105) 分別代表食品種類的數量以及需要計算的天數，兩者之間以空格分隔。

第二行包含 n 個整數 xj(1≤xj≤104)，代表第 j 種食品的重量，每個整數之間以空白分隔。

接下來的 q 行中，第 i 行包含一個正整數 ai(1≤ai≤2×109)，代表鯊鯊第 i 天所需的食物總重。

保證所有測資中的 n 以及 q 的和不會超過 1.5×105。

Output Format

對於每一筆測資的每一天，請輸出一行，包含一個整數，代表小意需要購買的最少食品數量，如果當天就算買下所有的鯊魚食品都沒辦法餵飽鯊鯊的話，請輸出 −1。

Sample Input 1

3
8 7
4 3 3 1 1 4 5 9
1
10
50
14
15
22
30
4 1
1 2 3 4
3
1 2
5
4
6

Sample Output 1

1
2
-1
2
3
4
8
1
1
-1

Hints

Problem Source

Codeforces 1676E

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~12 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
Submit
Back to Top