Teamwork

Source: USACO

Version: Phuoc Hung OJ Extended

Problem Statement

This package preserves the original task mechanism. Có $N$ học sinh với mức kỹ năng. Chia dãy theo thứ tự thành các nhóm liên tiếp, mỗi nhóm có nhiều nhất $K$ người. Điểm của nhóm bằng số người nhân kỹ năng lớn nhất trong nhóm. Hãy tối đa hóa tổng điểm.

Input

Dòng đầu chứa $N,K$. Dòng hai chứa $N$ mức kỹ năng.

Output

In tổng điểm lớn nhất.

Subtasks

• Subtask 1 — 20 points: small data.
• Subtask 2 — 30 points: medium data.
• Subtask 3 — 50 points: full PHOJ package limits.

Examples

Input

5 2
10 20 30 40 50

Output

170

Explanation

The output follows directly from the rules above.