Rat is the one !!!

0

0 votes
Binary Search, medium, Hard
Problem

New year comes with new hopes.... Just kidding!!! New year only comes with new problems (for you guys) and new anime (for me).

Every 12 years, mercenaries who possess the highest calibre of brute strength, cunning wit, and deadly precision gather to participate in the Junni Taisen. Each warrior bears the name and attributes of one of the 12 animals of the Chinese zodiac. With their pride and lives on the line, they engage in vicious combat until only the victor remains.

The war begins in a desolate city, devoid of any intelligent life form. The city has a total area N. Every warrior has a certain amount of influence. The warrior can then divide the influence that they have into a given portion of the area. Let the affected area be x, and the influence be y, then the influence per area will be floor(y/x). Let this quantity be the influence of war. Each area can only be influenced by a single warrior. If an area is not influenced by any warrior then the influence of war there is 0. The net influence of war is then the minimum of the influence of war of all the region combined. The goal here is to maximise this net influence of war.

The influence by a warrior can also be 0.

The first line contains no of test cases T. Then T lines follow each containing 13 values. The first one is N (that is area of the city) The next 12 are the influence that each warrior has (Ei).

output one line for each test case: The maximum possible of net influence of war.

Constraints:
T = 1e5
N <= 1e18
Ei <= 1e18

Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

let us see an example. suppose there are 2 warriors, and they have influence 5, 6. The total are of city is 4. Then to maximise the net influence of war, first warrior can influence an area of 2 with influence 2, and the second can influence an area 2 with influence 3. The minimum of the them would be 2, hence the net influence of war is 2, which is maximum possible net influence.

Editor Image

?