Pizza Party

All submissions for this problem are available.
Chef is planning a huge party for all of you and has ordered M pizzas. He wants to invite as many people to the party. However, he knows that everyone will have exactly one slice of a pizza (regardless of the size) and he wants to make sure that he has enough pizza slices.
Chef is very lazy and will only make a total of N straight cuts among all the pizzas. Each pizza is also of different size and to avoid the slices getting too small the chef can only make a max of A_{i} cuts to the i^{th} pizza. He wants to maximize the number of slices of pizza. Since chef is busy with preparing other aspects of the party he wants you to find out the maximum number of slices he can get following the constraints.
If a pizza is not cut at all then it is considered as 1 slice.
Input
First line contains two integers M and N. The second line of input contains the array A.
Output
Output a single integer  the maximum number of slices chef can get.
Constraints
 1 ≤ M ≤ 2*10^{5}
 1 ≤ N,A_{i} ≤ 2*10^{5}
Subtasks
 Subtask 1: 1 ≤ M,N ≤ 100  10 points
 Subtask 2: 1 ≤ N ≤ 100, 1 ≤ M ≤ 10^{5}  20 points
 Subtask 3: Original Constraints  70 points
Example
Input: 5 10 1 2 3 4 5 Output: 31
Explanation
Example case 1. One of the optimal way to cut would be to do {0, 1, 0, 4, 5} cuts.
Author:  yogesh01 
Tags  yogesh01 
Date Added:  9112017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 