409699: GYM103688 A Bookshelf Filling

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 $$$a$$$ and thickness $$$1$$$, and the type B with height $$$b~(a < b)$$$ and thickness $$$1$$$. The number of each type of book are $$$n$$$ and $$$m$$$ respectively. And he already knew the height of the bookshelf which is $$$h~(h \geq b)$$$.

In the beginning, he arranged all the books on the shelf in height-ascending order, which means the books of height $$$a$$$ are all on the left, and the books of height $$$b$$$ are all on the right. The total length these books occupied on the bookshelf will be $$$n + m$$$.

However, Joseph found there was still a vacancy on top of these books, so he prepared to select $$$k ~ (0 \leq k \leq m - 1)$$$ books with height $$$b$$$ 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 $$$T ~ (1 \leq T \leq 10^3)$$$. $$$T$$$ test cases follow.

For each test case, only one line contains five integers $$$a, b, n, m, h ~ (1 \leq a < b \leq h \leq 10^6, 1 \leq n,m \leq 10^9)$$$

For each test case, print a line contains one integer $$$w$$$, 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 $$$2,3$$$ and $$$4$$$.