1409B.md (1911B)
1 Source: https://codeforces.com/problemset/problem/1409/B 2 3 B. Minimum Product 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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: 22 23 * 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$. 24 25 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. 26 27 You have to answer $t$ independent test cases. 28 29 Input 30 31 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. 32 33 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. 34 35 Output 36 37 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. 38 39 Example 40 41 Input 42 43 ``` 44 7 45 10 10 8 5 3 46 12 8 8 7 2 47 12343 43 4543 39 123212 48 1000000000 1000000000 1 1 1 49 1000000000 1000000000 1 1 1000000000 50 10 11 2 1 5 51 10 11 9 1 10 52 ``` 53 54 Output 55 56 ``` 57 70 58 77 59 177177 60 999999999000000000 61 999999999 62 55 63 10 64 ``` 65 66 Note 67 68 In the first test case of the example, you need to decrease $b$ three times and obtain $10 \cdot 7 = 70$. 69 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$. 71 72 In the sixth test case of the example, you need to decrease $a$ five times and obtain $5 \cdot 11 = 55$. 73 74 In the seventh test case of the example, you need to decrease $b$ ten times and obtain $10 \cdot 1 = 10$.