연못

거북이 Syrup은 집 옆 연못에서 자주 헤엄친다. 오래전 빙하의 움직임으로 파인 이 연못은 좁고 곧아서 거의 강처럼 생겼지만, 물이 잔잔해 거북이가 양쪽으로 막힘없이 헤엄칠 수 있다.

오늘도 평소처럼 연못에 있던 Syrup은 두려운 초록 점 하나를 발견한다. 바로 피어오르는 조류 포자다. 폭우가 지나간 뒤 연못으로 쓸려 들어온 기름진 흙이 점차 분해되면서, 평소에는 얌전하던 토착 조류가 엄청나게 빠른 속도로 자랄 양분이 공급된다. 그대로 두면 이 조류가 번성해 수면 아래 호저 식물에 햇빛이 닿지 못하게 막을 수 있고, 몇 달 동안 물을 망칠 생태계 불균형이 시작된다.

다행히 Syrup은 이런 상황이 낯설지 않고, 드물게 생기는 이 문제에 대한 단순하지만 효과적인 해법을 알고 있다. 먹어버리는 것이다. Syrup은 조류가 피어오르기 시작한 일직선 연못의 흙 유입 지점 N곳을 찾았고, 이 지점들은 한쪽 끝에서 다른 쪽 끝까지 1번부터 N번까지 번호를 붙일 수 있다. i번째 지점과 (i + 1)번째 지점은 Di미터만큼 떨어져 있으며, Syrup은 처음 발견한 포자 옆인 K번째 지점에 있다. 이제 Syrup은 그 포자를 삼킨 뒤 두 방향 중 하나로 초속 1미터의 속도로 헤엄쳐 가면서 지나치는 조류 덩어리를 모두 먹어치워, 모든 조류를 없앨 것이다.

N개의 흙 유입 지점은 각각 조류 0가닥으로 시작하고, Syrup이 도착할 때까지 매초 1가닥씩 늘어난다. 거북이는 튼튼해서 Syrup은 조류가 몇 가닥이든 어렵지 않게 먹을 수 있다. 그러나 너무 자란 조류는 맛이 없으므로, 여행 동안 먹는 가닥 수를 최소로 하고 싶다. 연못을 따라 최선의 경로로 움직일 때, Syrup이 연못의 조류를 모두 없애기 위해 먹어야 하는 조류 가닥 수의 최솟값을 구하라.

프로그램은 표준 입력에서 읽는다.

첫째 줄에는 두 정수 N과 K가 주어진다.

둘째 줄에는 N − 1개의 정수가 주어진다. i번째 정수는 흙 유입 지점 i와 i + 1 사이의 거리 Di(미터)다.

프로그램은 표준 출력에 출력한다.

연못의 조류를 모두 없애기 위해 Syrup이 먹어야 하는 조류 가닥 수의 최솟값을 한 줄에 하나의 정수로 출력한다.

• 2 ≤ N ≤ 3 × 105
• 1 ≤ K ≤ N
• 1 ≤ Di ≤ 106