Problem

In Amazon EC2, there are n virtual machine (VMs) types, and each type has a limited number of instances available. Each time a VM instance is rented, the customer pays a fee equal to:

• the lowest non-zero availability among all VM types + the highest availability among all VM types.

There are m customers arriving one by one. Each customer always rents from the VM type that currently has the highest availability. After a rental, the availability of that VM type decreases by 1. The task is to determine the total revenue earned after serving all rental requests.

Input

• n: the number of virtual machine types
• vmStock: a list of integers representing the number of VMs of each type available initially
• m: the number of customers requesting to rent a VM

Output

• The total revenue earned after serving all rental requests

Constraints

• 1 <= n <= 100
• 0 <= vmStock[i] <= 100
• 1 <= m <= 100