Вам даны четыре целых числа \(a\), \(b\), \(x\) и \(y\). Изначально \(a \ge x\) и \(b \ge y\). Вы можете применить следующую операцию не более \(n\) раз:
- Выбрать \(a\) или \(b\) и уменьшить это число на единицу. Однако в результате этой операции значение \(a\) не может стать меньше \(x\), а значение \(b\) не может стать меньше \(y\).
Ваша задача — найти минимальное возможное произведение \(a\) и \(b\) (\(a \cdot b\)), которое можно получить, применив данную операцию не более \(n\) раз.
Вам необходимо ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите число: минимальное возможное произведение \(a\) и \(b\) (\(a \cdot b\)), которое можно получить, применив данную операцию не более \(n\) раз.
Примечание
В первом наборе тестовых данных примера нужно уменьшить \(b\) три раза и получить \(10 \cdot 7 = 70\).
Во втором наборе тестовых данных примера нужно уменьшить \(a\) один раз, \(b\) один раз и получить \(11 \cdot 7 = 77\).
В шестом наборе тестовых данных примера нужно уменьшить \(a\) пять раз и получить \(5 \cdot 11 = 55\).
В седьмом наборе тестовых данных примера нужно уменьшить \(b\) десять раз и получить \(10 \cdot 1 = 10\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
70
77
177177
999999999000000000
999999999
55
10
|