You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

Special for beginners, ^_^

Description

明明最近有点穷，于是选择倒卖套卡来赚点生活费。

一套卡有 n 种卡，第 i 种卡的数目为 c[i] 。

另外有一种特殊的卡：万能卡，简称 r 卡。它的数目是 m。 可以用每种卡各一张来组成一套卡，也可以用一张 r 卡和除了某一种卡以外的其他卡各一张组成 1 套卡 ， 这样顾客也会买账 。比如，当 n = 3 时，一共有 4 种合法的套卡：{ 1 , 2 , 3 } , { r , 2 , 3 } , { 1 , r , 3 } , { 1 , 2 , r } 。

给出 n ，m 和 c[i] ，现在明明需要组成尽量多的套卡。每张卡最多只能用在一副套卡里（可以有卡不使用）。

Format

Input

第一行包含两个整数 n ， m ， 即卡的种数和万能卡的个数 ；

第二行包含 n 个整数 c[i] ，即每种牌的张数 。

( 2 ≤ n ≤ 50 ， 0 ≤ m ， c[i] ≤ 5x10⁸) 。

Output

输出一个数字 ans ， 表示最多组成的套卡数量。

Samples

4 5
2 3 4 5

4

Limitation

2s, 1024KiB for each test case.