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 Ai cuts to the ith 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*105
- 1 ≤ N,Ai ≤ 2*105

-----Subtasks-----
- Subtask 1: 1 ≤ M,N ≤ 100 - 10 points 
- Subtask 2: 1 ≤ N ≤ 100, 
1 ≤ M ≤ 105 - 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.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
m,n=[int(i) for i in input().split()]
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True)
ans=0
w=0
q=m
for m in range(q):
    if(arr[m]>n):
        w=1
        break 
    ans+=1+(arr[m]*(arr[m]+1))//2
    n-=arr[m]

if(n==0):
    print(ans)
else:
    if(w==1):
        print(ans+q-m+(n*(n+1))//2)
    else:
        print(ans)

# cook your dish here
m,n=[int(i) for i in input().split()]
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True)
ans=0
w=0
q=m
for m in range(q):
    if(arr[m]>n):
        w=1
        break 
    ans+=1+(arr[m]*(arr[m]+1))//2
    n-=arr[m]

if(n==0):
    print(ans)
else:
    if(w==1):
        print(ans+q-m+(n*(n+1))//2)
    else:
        print(ans)

m,n=map(int,input().split());arr=sorted(list(map(int,input().split())),reverse=True);ans,w,q = 0,0,m
for m in range(q):
    if(arr[m]>n):w=1;break 
    ans+=1+(arr[m]*(arr[m]+1))//2;n-=arr[m]
print(ans) if(n==0) else print(ans+q-m+(n*(n+1))//2) if(w==1) else print(ans)

# cook your dish here
m,n=[int(i) for i in input().split()]
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True)
ans=0
w=0
q=m
for m in range(q):
    if(arr[m]>n):
        w=1
        break 
    ans+=1+(arr[m]*(arr[m]+1))//2
    n-=arr[m]

if(n==0):
    print(ans)
else:
    if(w==1):
        print(ans+q-m+(n*(n+1))//2)
    else:
        print(ans)



max_ = int(2e5)
def make_arr(dp):
    dp[1] = 2
    for i in range(2,max_):
        dp[i] = dp[i-1] +i
    
dp = [0]*(max_ +1)
make_arr(dp)
M,N = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
A.sort(reverse = True)
ans = 0
flag  = 0
for i in A:
    if(flag == 0):
        if(N >= i):
            ans  = ans + dp[i]
            N = N- i
        elif(N < i):
            ans = ans + dp[N]
            flag = 1
    else:
        ans = ans  +1
    
print(ans)


n,m=map(int,input().split())
slices=[int(x) for x in input().split()]
slices.sort()
array=[0]*(slices[-1]+1)
array[0]=1
for i in range(1,len(array)):
    array[i]=array[i-1]+i
total=0
slices=slices[::-1]
value=0
for i in range(len(slices)):
    if slices[i]<=m:
        total+=array[slices[i]]
        m-=slices[i]
        continue
    if m<slices[i]:
        total+=array[m]
        m=0
        value=len(slices)-i-1
        break
total+=value
print(total)