307756: CF1409B. Minimum Product

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Minimum Product

题意翻译

给定$a,b,x,y,n$,你可以进行至多$n$次操作,每次操作把$a$或$b$减一,但必须保证$a≥x$与$b≥y$始终成立,求$ab$的最小值。

题目描述

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.

输入输出格式

输入格式


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.

输出格式


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.

输入输出样例

输入样例 #1

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

输出样例 #1

70
77
177177
999999999000000000
999999999
55
10

说明

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

Input

题意翻译

给定$a,b,x,y,n$,你可以进行至多$n$次操作,每次操作把$a$或$b$减一,但必须保证$a≥x$与$b≥y$始终成立,求$ab$的最小值。

加入题单

上一题 下一题 算法标签: