题目描述

你正在打游戏。

要想通关，你需要消灭 n 个敌人。你需要消灭的第 i 个敌人具有 ai 点的血量。

初始时，你有 s 点的满血量。在任意时刻，你的血量可以为 0，但不能为负或超过 s。

消灭敌人，你需要消耗若干血量。每次消灭一个敌人，你所消耗的血量值由你来任意决定，假设第 i 个敌人你决定消耗的血量值为 xi，则消灭该敌人，你会得到 ai*xi 的积分。xi 可以为 0，但不能为负，也不能超过你当时已有的血量。并且，每次消灭一个敌人后，你可以回升 b 点血量（当恢复到满血量时不再回升）。

问：游戏通关后，你所能得到的积分之和最大可能是多少？

多组数据。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据：

—第一行包含整数 s，b，n，依次表示你的满血量、每次消灭一个敌人后回升的血量值、敌人的数量。

—接下来一行，包含 n 个整数 ai，依次表示第 i 个敌人的血量。

输出格式

共 T 行，每组数据的答案占一行。

样例输入

2
5 2 2
2 1
8 9 10
7 4 3 3 6 4 5 7 5 10

样例输出

12
432

样例解释

此处仅解释第一组数据：

初始时，你的满血量为 5。

消灭第一个敌人，你选择消耗 5 点血量，获得积分为 2×5=10，恢复后血量为 2；

消灭第二个敌人，你选择消耗 2 点血量，获得积分为 1×2=2。

总计获得 10+2=12 的积分。

数据范围

全部测试点满足：1 <= T <= 100, 1 <= n <= 5×10^5, 1 <= s, b <= 10^6, 1 <= ai <= 10^6。具体如下：