27085번 - 최대 점수

문제

리프는 던전을 탐험하는 게임을 하고 있다. 던전은 일렬로 배열된 $N$개의 방으로 이루어져 있으며, 리프는 초기에 $s$번째 방에 있다.

$s$번째 방을 제외한 모든 방에는 몬스터가 한 마리씩 살고 있다. 리프가 $i$번째 방에 도착했을 때 몬스터가 있다면 반드시 죽여야 하며, 이때 점수 $A_i$를 얻는다.

몬스터는 이동하지 않으며, 몬스터를 한 번 죽이면 다시 생성되지 않는다. 초기에 리프의 점수는 0이며, 점수가 0 미만이 되면 게임오버가 된다.

리프는 매 순간 다음과 같은 행동 중 하나를 할 수 있다.

• 현재 $i$번째 방에 있을 때, $i-1$번째 방으로 이동하기 (2ドル \le i \le N$)
• 현재 $i$번째 방에 있을 때, $i+1$번째 방으로 이동하기 (1ドル \le i \le N-1$)
• 던전을 탈출하기

게임오버가 일어나지 않을 때, 리프가 던전을 탈출하는 순간의 점수의 최댓값을 구하여라.

입력

첫 번째 줄에 정수 $N,ドル $s$가 주어진다.

두 번째 줄에 $N$개의 정수 $A_1, A_2, \ldots, A_N$이 주어진다.

출력

게임오버가 일어나지 않을 때, 리프가 던전을 탈출하는 순간의 점수의 최댓값을 첫 번째 줄에 출력한다.

제한

• 1ドル \le N \le 2 \times 10^5$
• 1ドル \le s \le N$
• $-10^9 \le A_i \le 10^9$ $(1 \le i \le N)$
• $A_s = 0$

힌트