카드 세트

시간 제한2초메모리 제한512 MB

요약

N개 카드 종류의 개수와 조커 개수가 주어질 때, 모든 종류를 하나씩 쓰는 덱 또는 한 종류를 빼고 조커를 쓰는 덱을 최대 몇 개 만들 수 있는지 구한다.

난이도: 보통10점 중 7점
유형: 이분 탐색, 그리디, 수학, 구현
정답자: 아직 제출이 없습니다

문제

카드의 종류 수 $N$ 과 각 종류의 카드가 몇 장인지, 그리고 조커 카드가 몇 장인지 주어진다. 이 카드로 덱(deck)을 만든다. 하나의 덱은 다음 두 유형 중 하나다.

모든 종류의 카드를 한 장씩 모은 덱. 조커 카드는 쓰지 않는다.
한 종류를 빼고 나머지 종류의 카드를 한 장씩 모은 뒤 조커 카드 한 장을 더한 덱.

예를 들어 카드가 3종류이고 조커가 한 장 있으면 {1번 카드, 2번 카드, 3번 카드}, {조커, 2번 카드, 3번 카드}, {1번 카드, 조커, 3번 카드}, {1번 카드, 2번 카드, 조커}가 모두 덱이 된다. 카드 한 장은 덱 하나에만 들어갈 수 있다. $N$ 이 1이면 두 번째 유형의 덱은 조커 카드 한 장만으로 이루어진다.

주어진 카드로 만들 수 있는 덱의 최대 개수를 구하시오.

입력

첫째 줄에 카드의 종류 수 $N$ 이 주어진다. $N$ 은 50 이하의 자연수다.

둘째 줄에 정수 $N$ 개가 주어진다. 그중 $k$ 번째 수는 $k$ 번 종류의 카드가 몇 장인지 나타낸다. 각 값은 0 이상 5억 이하다.

셋째 줄에 조커 카드가 몇 장인지 주어진다. 0 이상 5억 이하다.

출력

만들 수 있는 덱의 최대 개수를 정수 하나로 출력한다.

예제2

예제 1
입력
```
2
10 15
3
```
예상 출력
```
13
```
예제 2
입력
```
1
7
4
```
예상 출력
```
11
```