Recently, Joseph bought lots of books and was going to put them all on the shelf. He found that there are only two types of books -- the type A with height  and thickness , and the type B with height  and thickness . The number of each type of book are  and  respectively. And he already knew the height of the bookshelf which is .
In the beginning, he arranged all the books on the shelf in height-ascending order, which means the books of height  are all on the left, and the books of height  are all on the right. The total length these books occupied on the bookshelf will be . 
However, Joseph found there was still a vacancy on top of these books, so he prepared to select  books with height  from the rightmost side and put them all horizontally on top of other books to reduce the length they occupied. He wanted to know the minimum width if he arranges these books optimally.  

The first line of the input gives the number of test cases .  test cases follow.
For each test case, only one line contains five integers .

For each test case, print a line contains one integer , indicating the minimum width.

4
2 5 5 8 5
2 4 5 7 5
2 6 5 2 6
3 4 3 2 5

10
8
7
4

The following pictures from left to right show the possible arrangement of books for the testcases  and .