분탕의 신 아이보리 3

나도리는 들판에서 뛰어놀며 가로 $N$칸짜리 컨테이너를 가지고 놀고 있었다. 각 칸에는 가장 왼쪽에서 시작해 $1$번부터 $N$번까지의 번호가 붙어 있고, $i$번 칸 안에는 정수 $A_i$가 적혀 있다.

이를 아니꼽게 본 아이보리가 두 번의 빔을 날려 컨테이너에 분탕을 치려고 한다. 나도리는 아래와 같은 과정을 통해 자신의 몸을 던져 빔을 막아내려고 한다.

1. 나도리가 $p_1$번 칸에 자리를 잡는다.
2. 아이보리가 $1$번 칸 왼쪽에서 $N$번 칸을 향해 첫째 빔을 발사한다. 빔은 나도리한테 막혀서 번호가 $p_1$보다 작은 모든 칸에 적힌 수에 $-1$을 곱한다.
3. 나도리가 $p_2$번 칸에 자리를 잡는다.
4. 아이보리가 $N$번 칸 오른쪽에서 $1$번 칸을 향해 둘째 빔을 발사한다. 빔은 나도리한테 막혀서 번호가 $p_2$보다 큰 모든 칸에 적힌 수에 $-1$을 곱한다.

오히려 기회라 생각한 나도리는 적절한 위치에서 빔을 막아 분탕 후 수열의 원소의 합을 최대로 만들고자 한다. 하지만 나도리는 배가 고파 첫 번째 빔을 막은 자리에서 최대 $K$칸까지만 움직일 수 있다.

나도리를 위해 분탕 후 수열의 합을 최대로 하는 방법을 알려주자!

첫 번째 줄에 컨테이너 칸의 개수 $N$, 나도리가 움직일 수 있는 거리를 나타내는 정수 $K$가 공백으로 구분되어 주어진다. $(1 \le K \le N \le 200\,000)$

두 번째 줄에 $N$개의 칸에 적힌 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(-10\,000 \le A_i \le 10\,000)$

첫 번째 줄에 분탕 후 수열의 합의 최댓값을 출력한다.

두 번째 줄에 첫째 빔을 발사할 때 나도리의 위치한 칸의 번호 $p_1$, 둘째 빔을 발사할 때 나도리의 위치 $p_2$를 공백으로 구분하여 출력한다. 가능한 위치가 여러 가지라면 $p_1$이 가장 작은 것을, $p_1$이 같은 것 중에서는 $p_2$가 가장 작은 것을 출력한다. $\left(1 \le p_1, p_2 \le N; \left\vert p_1 - p_2 \right\vert \le K \right)$