
ZOJ Problem Set  3997
People in Wonderland love watching movies. Recently, a very popular movie called Despicable Me 3 is on show and people can't wait to enjoy it in the cinema. Obviously, everyone loves to take a seat in the row that is neither too far nor too near from the screen. You are the manager of a local cinema. Today, you have received many requests to book seats in a certain row. For convenience, let's number the seats in that row from 1 to \(M\). People in Wonderland are crazy about maths, so they just want their seat number to be a multiple of a certain number. Each seat can only be taken by at most one person. You have known that for \(i\) from 1 to 10, there are \(A_i\) people wanting their seat numbers to be a multiple of \(i\). You task is to make full use of your math skills to satisfy as many people as possible. InputThe first line contains a single interger \(T\) (about \(10^4\)), indicating the number of test cases. For each test case: The first line contains a positive interger \(M\) (\(1 \le M \le 10^9\)), indicating the number of seats in the row. the second line contains 10 integers \(A_1, A_2, \dots, A_{10}\) (\(0 \le A_i \le 10^9\)), indicating that there are \(A_i\) people wanting their seat numbers to be a multiple of \(i\). OutputFor each case output one integer, indicating the maximum number of requests you can satisfy. Sample Input2 10 2 1 4 0 0 0 0 0 0 0 6 0 2 0 1 0 0 0 0 0 0 Sample Output6 3 Hint
The first sample:
The second sampleļ¼ Author: LIU, Zhenwei Source: ZOJ Monthly, January 2018 