Cutting Metal Surplus

Given several metal rods, the cost of each cut, and the sale price per unit length. You may choose one positive integer saleLength; rods can be cut into pieces of length saleLength, and any leftover scrap is discarded with no revenue. You may leave a rod unprocessed. The goal is to maximize the total sales revenue minus the cutting costs.

输入格式

The first line contains n, costPerCut, salePrice; the second line contains n rod length values. Original ranges: 1≤n≤50, 1≤length[i]≤10000, 1≤costPerCut,salePrice≤100. This site explicitly lets each rod independently choose how many finished saleLength pieces to keep. When a rod divides evenly and is fully used, the last piece needs no cut to separate it; when there is scrap or only some of the pieces are kept, each finished piece requires one cut, and scrap earns nothing.

输出格式

Output the maximum achievable total profit.

样例 1

输入：

3 1 10
30 59 110

输出：

1913

样例 2

输入：

3 100 10
26 103 59

输出：

1230

样例 3

输入：

1 100 1
1

输出：

1