매트릭스 최적화

매트릭스를 지탱하는 인공지능은 복잡한 시스템이라, 아키텍트가 이를 최적화해 보기로 했다.

이 시스템은 $n$개의 노드가 순서대로 연결된 형태로 나타낼 수 있다. 각 노드에는 특별한 특성 $w_i$, 즉 연산 중요도가 있다.

아키텍트는 노드 하나를 골라 그 작용을 양쪽 방향으로 각각 $k$개의 인접 노드까지 퍼뜨린다. 어느 한쪽 방향의 노드가 $k$개보다 적으면, 있는 만큼만 퍼뜨린다. 작용이 퍼진 노드의 총수를 $d$라 하자. 그러면 선택한 노드의 연산 중요도는 $(1 + d) \cdot w_i$가 되고, 작용이 퍼진 노드들의 연산 중요도는 0이 된다.

이 작업을 수행해 얻을 수 있는 시스템의 연산 중요도 합의 최댓값을 구하라.

첫 줄에 두 정수 $n$과 $k$가 주어진다. $n$은 연산 노드의 개수이고, $k$는 선택한 노드의 작용이 한쪽 방향으로 퍼지는 노드 수이다. ($1 \le n \le 2 \cdot 10^5$; $0 \le k \le 2 \cdot 10^5$)

둘째 줄에는 공백으로 구분된 양의 정수 $w_1, w_2, \dots, w_n$이 주어진다. 각 값은 노드의 연산 중요도이다. ($1 \le w_i \le 5 \cdot 10^5$)

시스템의 연산 중요도 합의 최댓값을 정수 하나로 출력한다.