Laundry

Time limit2sMemory limit1024 MB

Summary

Given seven pile sizes for the programme combinations and a load capacity k, find the minimum number of loads, where each load uses one of programmes A, B, or C.

Level: Medium6 of 10
Topics: Math, Greedy
Solved: No attempts yet

Problem

Every Sunday is laundry day, and there is always a huge pile of clothes waiting to be washed. It is certainly going to take you forever. You are particularly annoyed by how careful you have to be when washing certain items, and how important it is to choose an appropriate washing programme for each item.

Fortunately, your washing machine is quite old and only supports three washing programmes: A, B, and C. You can put at most $k$ items in one load, and each load is washed with one of the programmes.

Some items are easy to care for, and you can put them in any load you like. More delicate items must not be washed with a specific programme, but the other two are fine. The worst clothes are the ones for which only one programme is appropriate.

You have already sorted the items into seven piles, where each pile holds items that accept the same combination of programmes. You know how many items are in each pile.

What is the minimum number of loads you need to wash?

Figure L.1: Illustration of Sample Input 2 with an optimal solution. The figure on the left shows seven piles, one for each combination. The figure on the right shows a possible optimal solution, where each pile is washed in one load. The numbers on the pile represent how many items of each combination are washed with this load. The leftmost pile is washed using programme A, the two piles in the middle with programme B, and the two piles on the right with programme C. So five loads are needed to wash all items, which is optimal since there are 15 items in total.

Input

The first line contains an integer $t$ ( $1 \leq t \leq 10^4$ ), the number of test cases. Then for each test case:

One line with an integer $k$ ( $1 \leq k \leq 10^9$ ), the number of items you can put in one load.
One line with seven integers $c_1, \ldots, c_7$ ( $0 \leq c_i \leq 10^9$ ), the number of items for each combination of programmes. The integers are given in this order: A, B, C, AB, BC, AC, ABC. For example, $c_4$ must be washed using either programme A or programme B.

Output

For each test case, output the minimum number of loads needed to wash all clothes.

Examples2

Example 1

Input

4
10
15 11 9 5 2 7 1
120
0 0 0 0 0 0 0
6
5 6 8 9 1 0 0
1213
295053681 137950336 87466375 956271897 344992260 31402049 988259763

Expected output

Example 2
Input
```
1
3
1 2 1 3 3 2 3
```
Expected output
```
5
```