문제 설명
최근 '3분 그래프'를 접한 jbs33_PJW는 깊은 감명을 받고 바로 상품을 주문했다.
그러나 성격이 급해 참지 못한 나머지, 모든 정점에서 동시에 불을 붙여 그래프를 익혔다.
따라서 모든 간선에 대하여 동시에 양쪽에서 불이 붙기 시작하며,
불은 1초에 길이 1만큼의 간선을 익힌다.
예를 들어, 길이가 4인 간선을 익히기 시작하면,
다음과 같이 2초 후 간선이 완전히 익게 된다.
모든 간선이 익는 데 걸리는 시간을 구하시오.
그러나 성격이 급해 참지 못한 나머지, 모든 정점에서 동시에 불을 붙여 그래프를 익혔다.
따라서 모든 간선에 대하여 동시에 양쪽에서 불이 붙기 시작하며,
불은 1초에 길이 1만큼의 간선을 익힌다.
예를 들어, 길이가 4인 간선을 익히기 시작하면,
다음과 같이 2초 후 간선이 완전히 익게 된다.
모든 간선이 익는 데 걸리는 시간을 구하시오.
입력 설명
첫째 줄에 간선의 개수 N이 주어진다. (1 ≤ N ≤ 1000)
둘째 줄에 N개의 간선의 길이가 각각 공백을 두고 주어진다.
(단, 모든 간선의 길이는 0 이상 109 이하의 짝수만 주어진다.)
둘째 줄에 N개의 간선의 길이가 각각 공백을 두고 주어진다.
(단, 모든 간선의 길이는 0 이상 109 이하의 짝수만 주어진다.)
출력 설명
첫 번째 줄에 모든 간선이 익는 데 걸리는 시간을 출력한다.
입력 예시 Copy
5
2 6 10 20 14
출력 예시 Copy
10
도움
예시 입력에서 간선이 익는데 걸리는 시간은 각각
1초, 3초, 5초, 10초, 7초이다.
1초, 3초, 5초, 10초, 7초이다.