Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3997
Seat Assignment

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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.

#### Input

The 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$.

#### Output

For each case output one integer, indicating the maximum number of requests you can satisfy.

#### Sample Input

2
10
2 1 4 0 0 0 0 0 0 0
6
0 2 0 1 0 0 0 0 0 0


#### Sample Output

6
3


#### Hint

The first sample:
There are 10 seats numbered from 1 to 10.
There are 2 people wanting their seat number to be a multiple of 1, 1 person wanting his seat number to be a multiple of 2, and 4 people wanting their seat number to be a multiple of 3.
The 2 people wanting their seat number to be a multiple of 1 can take seats numbered 1 and 4.
The only person wanting his seat number to be a multiple of 2 can take seat numbered 2.
The 3 people wanting their seat number to be a multiple of 2 can take seats numbered 3, 6, 9.

The second sampleļ¼
The 2 people wanting their seat number to be a multiple of 2 can take seats numbered 2, 6.
The only person wanting his seat number to be a multiple of 4 can take seat numbered 4.

Author: LIU, Zhenwei
Source: ZOJ Monthly, January 2018
Submit    Status