The earnings of gold through mining is 'x' units of gold per day. There are 'n' machines available that can be bought and the cost of the ith machine is arr[i] units of gold. It can be decided to buy any machine on any day if there is a sufficient amount of gold to buy that machine and any ith machine can be bought only once. Also, Each machine extracts extra 'z' units of gold per day, i.e. if there are 'j' machines then one can get (x + j * z) units of gold per day. Note that you can buy multiple machines on the same day.

Initially, there is no gold. Find the maximum amount of gold that one can get at the end of 'k' days.

Parameters:

x: an integer denoting units of gold you earn per day

z: an integer denoting units of gold, machine extract per day

arr[arr[0],...arr[n-1]]: An array of integers denoting the costs of all machines

k: an integer denoting the number of days

Example 1:

Input:

x = 1, z = 2, n = 3, arr = [3,2,4], k = 5

Output:

10

Explanation:

Day 1: Earn 1 unit of gold. Current amount of gold = 1

Day 2: Earn 1 unit of gold. Current amount of gold = 2

Day 3: Buy machine 1 at the start of day 3 which cost arr[1] = 2 units of gold. Current amount of gold = 2 — 2 + (1 + 2 x 1) = 3.

Day 4: Buy machine 0 at the start of day 4 which cost arr[0] = 3 units of gold. Current amount of gold = 3 — 3 + (1 + 2 x 2) = 5.

Day 5: Earn 5 units of gold (1 through mining and 4 through 2 machines bought). Final amount of gold = 5 + 5 = 10.

Example 2:

Input:

x = 3, z = 2, n = 3, arr = [4,2,3], k = 4

Output:

17

Explanation:

Day 1: Earn 3 units of gold. Current amount of gold = 3.

Day 2: Buy machine 2 at the start of day 2 which cost arr[2] = 3 units of gold. Current amount of gold = 3 — 3 + (3 + 2 x 1) = 5.

Day 3: Buy machine 1 at the start of day 3 which cost arr[1] = 2 units of gold. Current amount of gold = 5 — 2 + (3 + 2 x 2) = 10.

Day 4: Earn 7 units of gold (3 through mining and 4 through 2 machines bought). Final amount of gold = 10 + 7 = 17.

Example 3:

Input:

x = 8, z = 3, n = 3, arr = [7,7,7], k = 2

Output:

16

Explanation:

Day 1: Earn 8 units of gold. Current amount of gold = 8.

Day 2: Earn 8 units of gold (only through mining). Final amount of gold = 8 + 8 = 16

Constraints:

1 <= n <= 10^5

1 <= arr[i] <= 10^5

1 <= x , z <= 10^5

1 <= k <= 10^5

Someone please tell the approach and the solution to this problem.