시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB43816515243.804%

문제

길이가 $N$인 수열 $A$의 원소들을 원형의 다이얼에 기준점의 오른쪽부터 차례대로 나열한 형태를 다이얼 룰렛이라고 하자. 건덕이는 다이얼을 회전해 점수를 얻을 수 있다. 다이얼을 시계 방향 또는 반시계 방향으로 한 칸 돌리는 것을 회전이라고 하며, 이때 기준점을 지나치는 수를 점수에 더한다.

건덕이가 다이얼 룰렛을 $K$번 회전해 점수를 최대로 얻을 수 있도록 도와주자.

입력

첫째 줄에 수열 $A$의 길이 $N$과 회전 횟수 $K$가 공백으로 구분되어 주어진다. $(1\leq N\leq 200,000;$ $1\leq K\leq 10^9)$

둘째 줄에 수열 $A$의 원소 $A_i$가 공백으로 구분되어 주어진다. $\left(1\leq A_i\leq 10^9\right)$

출력

건덕이가 다이얼 룰렛을 $K$번 회전해 얻을 수 있는 점수의 최댓값을 출력한다.

예제 입력 1

5 4
1 4 2 1 2

예제 출력 1

13

예제 입력 2

5 10
999999991 999999959 999999985 999999960 999999957

예제 출력 2

9999999910

노트

초기 상태에서 시계 방향으로 $1$번 회전하면 $A_N$만큼의 점수를 얻는다.