Eating Queries Codeforces Solution | Codeforces Problem Solution 2022

Eating Queries Codeforces Solution | Codeforces Problem Solution 2022

E. Eating Queries

time limit per test

3.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Timur has 𝑛$n$ candies. The 𝑖$i$-th candy has a quantity of sugar equal to 𝑎𝑖$a_i$. So, by eating the 𝑖$i$-th candy, Timur consumes a quantity of sugar equal to 𝑎𝑖$a_i$.

Timur will ask you 𝑞$q$ queries regarding his candies. For the 𝑗$j$-th query you have to answer what is the minimum number of candies he needs to eat in order to reach a quantity of sugar greater than or equal to 𝑥𝑗$x_j$ or print -1 if it's not possible to obtain such a quantity. In other words, you should print the minimum possible 𝑘$k$ such that after eating 𝑘$k$ candies, Timur consumes a quantity of sugar of at least 𝑥𝑗$x_j$ or say that no possible 𝑘$k$ exists.

Solution Click Below:-  CLICK HERE

Note that he can't eat the same candy twice and queries are independent of each other (Timur can use the same candy in different queries).

Input

The first line of input contains a single integer 𝑡$t$ (1≤𝑡≤1000$1\le t\le 1000$)  — the number of test cases. The description of test cases follows.

The first line contains 2$2$ integers 𝑛$n$ and 𝑞$q$ (1≤𝑛,𝑞≤1.5⋅105$1\le n,q\le 1.5\cdot {10}^5$) — the number of candies Timur has and the number of queries you have to print an answer for respectively.

Lucky? Codeforces Solution

Equal Candies Codeforces Solution

Most Similar Words Codeforces Solution

X-Sum Codeforces Solution

Eating Queries Codeforces Solution

Longest Strike Codeforces Solution

White-Black Balanced Subtrees Codeforces Solution

Maximum Crossings (Easy Version) Codeforces Solution

Maximum Crossings (Hard Version) Codeforces Solution

The second line contains 𝑛$n$ integers 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ (1≤𝑎𝑖≤104$1\le a_i\le {10}^4$) — the quantity of sugar in each of the candies respectively.

Then 𝑞$q$ lines follow.

Each of the next 𝑞$q$ lines contains a single integer 𝑥𝑗$x_j$ (1≤𝑥𝑗≤2⋅109$1\le x_j\le 2\cdot {10}^9$) – the quantity Timur wants to reach for the given query.

It is guaranteed that the sum of 𝑛$n$ and the sum of 𝑞$q$ over all test cases do not exceed 1.5⋅105$1.5\cdot {10}^5$.

Output

For each test case output 𝑞$q$ lines. For the 𝑗$j$-th line output the number of candies Timur needs to eat in order to reach a quantity of sugar greater than or equal to 𝑥𝑗$x_j$ or print -1 if it's not possible to obtain such a quantity.

Join Now for Solution:-