라운드
면접 대비시간 제한1초메모리 제한512 MB
각 라운드에서 i번 회원을 제외한 모든 회원이 i번 회원에게 S 크레딧을 주고, 임의의 라운드 종료 시점에서 최솟값을 게임 결과라 할 때 이 최솟값의 최댓값을 구한다.
문제
인기 있는 온라인 모임 PerfectShape는 전 세계의 운동과 건강한 생활 방식을 좋아하는 사람들이 모인 곳이다. 모임의 모든 회원은 인기 있는 온라인 스포츠 플랫폼 M0V3에서 일정량의 크레딧을 획득했고, 이를 통해 다양한 운동 및 휴식 콘텐츠를 이용할 수 있다.
그런데 보유한 크레딧의 양은 사람마다 크게 다를 수 있다. PerfectShape 회원들은 공유와 연대를 중시하기 때문에, 다음과 같은 게임을 하며 크레딧을 재분배하기로 한다.
모임의 회원 N명에게 1번부터 N번까지 번호가 붙어 있고, 게임은 어떤 정수 k(1 ≤ k ≤ N)에 대해 k개의 라운드로 이루어진다. 게임의 i번째 라운드에서 i번 회원을 제외한 모든 회원이 i번 회원에게 S 크레딧을 준다. 게임은 어느 라운드가 끝난 뒤에도 종료할 수 있으며, 그 결과는 해당 라운드가 끝난 뒤 모임의 한 회원이 보유한 크레딧의 최솟값이다.
가능한 모든 게임 종료 시점 중에서 게임 결과로 얻을 수 있는 최댓값을 구하라.
입력
첫째 줄에 두 정수 N과 S가 주어진다. 다음 N개의 줄에는 각각 하나의 정수가 주어지며, (i + 1)번째 줄에는 i번 회원이 처음에 보유한 크레딧 Ci가 주어진다.
출력
게임 결과로 얻을 수 있는 최댓값 C를 한 줄에 출력한다.
제한
- 1 ≤ N ≤ 100 000
- 1 ≤ S ≤ 100 000 000
- 모든 i에 대해 1 ≤ Ci ≤ 100 000 000이고 S × (N − 1) ≤ Ci이다.
힌트
게임은 다음과 같이 진행된다.
- 1라운드가 끝난 뒤 보유한 크레딧은 44, 32, 28이고 최솟값은 28이다.
- 2라운드가 끝난 뒤 보유한 크레딧은 34, 52, 18이고 최솟값은 18이다.
- 3라운드가 끝난 뒤 보유한 크레딧은 24, 42, 38이고 최솟값은 24이다.
따라서 가능한 최선의 결과는 28이며, 이는 1라운드가 끝난 뒤 게임을 종료한 경우에 해당한다.