Homework from the algorithmic cource ("Tower", BMSTU).
Show the task condition
Vasiliy likes to rest after a hard work, so you may often meet him in some bar nearby. As all programmers do, he loves the famous drink "Beecola", which can be bought in n different shops in the city. It's known that the price of one bottle in the shop i is equal to xi coins.
Vasiliy plans to buy his favorite drink for q consecutive days. He knows, that on the i-th day he will be able to spent mi coins. Now, for each of the days he want to know in how many different shops he can buy a bottle of "Beecola".
The first line contains single integer n (1 ≤ n ≤ 100,000) — number of shops.
The second line contains n integers xi (1 ≤ xi ≤ 100,000) — prices in i-th shop.
The third line contains single integer q (1 ≤ q ≤ 100,000) — number of days.
Then follow q lines with integers mi (1 ≤ mi ≤ 109) — daily budget.
Print q integers where i-th number equals to number of shops where xi ≤ mi.
Show the task condition
You are facing the final boss in your favorite video game. The boss enemy has h health. Your character has n attacks. The i'th attack deals ai damage to the boss but has a cooldown of ci turns, meaning the next time you can use this attack is turn x+ci if your current turn is x. Each turn, you can use all attacks that are not currently on cooldown, all at once. If all attacks are on cooldown, you do nothing for the turn and skip to the next turn.
Initially, all attacks are not on cooldown. How many turns will you take to beat the boss? The boss is beaten when its health is 0 or less.
The first line contains t
(1≤t≤104) – the number of test cases.
The first line of each test case contains two integers h and n (1≤h,n≤2⋅105) – the health of the boss and the number of attacks you have.
The following line of each test case contains n integers a1,a2,...,an (1≤ai≤2⋅105) – the damage of your attacks.
The following line of each test case contains n integers c1,c2,...,cn (1≤ci≤2⋅105) – the cooldown of your attacks.
It is guaranteed that the sum of h
and n over all test cases does not exceed 2⋅105.
For each test case, output an integer, the minimum number of turns required to beat the boss.