Minimum Product

1000ms

262144K

Description:

You are given four integers $$$a$$$, $$$b$$$, $$$x$$$ and $$$y$$$. Initially, $$$a \ge x$$$ and $$$b \ge y$$$. You can do the following operation no more than $$$n$$$ times:

Choose either $$$a$$$ or $$$b$$$ and decrease it by one. However, as a result of this operation, value of $$$a$$$ cannot become less than $$$x$$$, and value of $$$b$$$ cannot become less than $$$y$$$.

Your task is to find the minimum possible product of $$$a$$$ and $$$b$$$ ($$$a \cdot b$$$) you can achieve by applying the given operation no more than $$$n$$$ times.

You have to answer $$$t$$$ independent test cases.

Input:

The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The only line of the test case contains five integers $$$a$$$, $$$b$$$, $$$x$$$, $$$y$$$ and $$$n$$$ ($$$1 \le a, b, x, y, n \le 10^9$$$). Additional constraint on the input: $$$a \ge x$$$ and $$$b \ge y$$$ always holds.

Output:

For each test case, print one integer: the minimum possible product of $$$a$$$ and $$$b$$$ ($$$a \cdot b$$$) you can achieve by applying the given operation no more than $$$n$$$ times.

Sample Input:

7
10 10 8 5 3
12 8 8 7 2
12343 43 4543 39 123212
1000000000 1000000000 1 1 1
1000000000 1000000000 1 1 1000000000
10 11 2 1 5
10 11 9 1 10

Sample Output:

70
77
177177
999999999000000000
999999999
55
10

Note:

In the first test case of the example, you need to decrease $$$b$$$ three times and obtain $$$10 \cdot 7 = 70$$$.

In the second test case of the example, you need to decrease $$$a$$$ one time, $$$b$$$ one time and obtain $$$11 \cdot 7 = 77$$$.

In the sixth test case of the example, you need to decrease $$$a$$$ five times and obtain $$$5 \cdot 11 = 55$$$.

In the seventh test case of the example, you need to decrease $$$b$$$ ten times and obtain $$$10 \cdot 1 = 10$$$.

Informação

Provedor Codeforces

Código CF1409B