Problem
Tom Sawyer는 n명의 친구를 설득하여 Polly 숙모의 집을 둘러싼 울타리를 칠하는 어려운 작업을 돕도록 했습니다. 울타리는 1에서 k까지 번호가 매겨진 k개의 연속된 보드로 구성되며 k번째 보드 다음에 다시 첫 번째 보드가 옵니다.
Tom의 친구들은 매우 까다롭습니다. i번째 친구는 정확히 ai 연속 보드의 한 부분을 칠할 수 있는 경우에만 페인팅에 참여하는 데 동의합니다. Tom에는 브러시가 하나뿐이므로 친구들이 차례대로 할당된 전체 세그먼트를 한 번에 칠합니다. Tom이 할 일은 친구들을 초대할 순서를 선택하고 각각에 대해 원하는 연속 보드 수를 선택하는 것뿐입니다.
동시에 Tom의 각 친구는 도색되지 않은 울타리 판자와 그의 전임자 중 한 명이 이미 칠한 판자를 모두 칠할 준비가 되어 있습니다. 그러나 친구들은 도색되지 않은 판에 그림을 그리면서 더 많은 즐거움을 얻습니다. Tom은 숫자 x를 선택하고 각 친구가 칠하지 않은 판자 x개 이상을 칠하는 방식으로 칠할 울타리 섹션을 배포하려고 합니다. Tom은 친구들을 매우 사랑하고 그들 각자가 울타리를 칠하는 것을 최대한 활용하기를 원하기 때문에 x를 최대화하려고 합니다.
Tom이 친구들에게 얼마나 큰 기쁨을 줄 수 있는지 이해하도록 도와주세요.
입력 데이터 형식
입력 파일의 첫 번째 줄에는 두 개의 정수 n(1 ≤ n ≤ 10
5 ) 및 k(1 ≤ k ≤ 10
9 )가 포함됩니다. 다음 줄에는 n개의 정수가 포함됩니다. — 값 a
i (1 ≤ a
i ≤ k).
출력 데이터 형식
하나의 숫자 인쇄 –
x의 가능한 최대값.
<몸>
| 입력 |
출력 |
2100
5 10
| 5 |
4 10
7 8 3 5
| 2 |
설명
첫 번째 예에서 친구 중 한 명이 보드를 5개 이상 칠하고 싶지 않기 때문에 x = 5입니다. 그는 먼저 와서 다섯 개를 칠한 다음 칠하지 않은 또 다른 10 개의 보드가 Tom의 두 번째 친구에게 갈 것입니다. 나머지 85개의 보드는 Tom이 직접 칠해야 합니다.
두 번째 예에서 x = 2는 예를 들어 다음과 같이 도달할 수 있습니다. 먼저 세 번째 친구는 4~6번 보드(도색되지 않은 보드 3개)를 칠합니다. 그런 다음 네 번째 친구는 보드 1에서 5(도색되지 않은 보드 3개)를 칠합니다. 그런 다음 두 번째 친구는 보드 1에서 8(도색되지 않은 보드 2개)을 칠합니다. 마지막으로, 첫 번째 친구는 보드 6에서 10 및 1에서 2까지 칠합니다(도색되지 않은 보드 2개, 울타리는 순환하며 이 보드는 연속 세그먼트를 형성합니다).