题目描述

著名商店“Second Food”每月只营业两天出售杂货，并且这两天的价格各不相同。你想为一个月购买 $n$ 公斤土豆。你知道在本月的第一天，每公斤土豆的价格为 $a$ 个硬币，第二天为 $b$ 个硬币。在“Second Food”你可以购买任意整数公斤的土豆。

幸运的是，“Second Food”在本月第一天对土豆推出了一个促销活动——每买 $m$ 公斤土豆，就额外赠送 $1$ 公斤！换句话说，你只需支付 $m$ 公斤的价格，就能获得 $m+1$ 公斤。

请你计算，至少买到 $n$ 公斤土豆所需花费的最少硬币数。

输入格式

每组测试数据包含多组测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10\,000$）。接下来是每组测试用例的描述。

每组测试用例的第一行包含两个整数 $a$ 和 $b$（$1 \leq a, b \leq 10^9$），分别表示第一天和第二天每公斤土豆的价格。

第二行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^9$），分别表示你需要购买的土豆总量，以及促销活动中需要购买的公斤数。

输出格式

对于每组测试用例，输出一行一个整数，表示至少买到 $n$ 公斤土豆所需花费的最少硬币数。

说明/提示

在第一个测试用例中，第一天你买 1 公斤并通过促销再获得 1 公斤。第二天你再买 1 公斤土豆。这样你总共花费 $5+4=9$ 个硬币。

在第二个测试用例中，第一天你买 2 公斤并通过促销再获得 1 公斤。这样你总共花费 $2 \times 5 = 10$ 个硬币。

由 ChatGPT 4.1 翻译

样例

5
5 4
3 1
5 4
3 2
3 4
3 5
20 15
10 2
1000000000 900000000
1000000000 8

9
10
9
135
888888888900000000