Codeforces Round 667 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

greedy

math

*1100

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Minimum Product

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Example

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

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/19/2024 09:56:21 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|