题目描述

我们假设小 T 有一个人体耐力上限 $E$，在月初的时候，小 T 有 $E$ 的体力。

接下来每一天有一个任务，这个任务小 T 可以付出任意的非负整数体力去完成，并且，每一天的结束的时候，小 T 会增加 $R$ 的体力。当然体力是不可能超出 $E$ 的，也就是说，如果当前体力 $+R$ 大于 $E$，那么恢复完之后的体力依旧是 $E$。毫无疑问，体力是不可能小于 $0$ 的。

每个任务会有一个价值 $v_i$，一个任务的收获就是这个任务的价值乘上付出的体力。

你要帮帮小 T，使他最大化所有任务的收获之和，方便他继续的高富帅！最后，我们的口号是“烧死 GFS$\sim$”。

输入格式

本题存在多组数据。

第一行一个正整数 $Case$，表示数据的组数。

对于每一组数据，第一行有三个正整数 $E,R,n$，表示的是能量上限，恢复值，和这个月的天数。第二行有 $n$ 个非负整数表示 $v_1 \dots v_n$。

输出格式

对于每一组数据，输出一行，即最大化的收获之和。

1
5 2 2
2 1

12

样例说明

第一天用 $5$ 的体力，接下来恢复 $2$ 点体力，再用光。

数据规模与约定

对于 $100\%$ 的数据，$Case\le10$，$1\le n\le 5\times 10^5$，$E\le 10^6$，$v_i\le 10^6$，所有输入均非负。

题目来源

By 佚名提供