Description

小W闲来无事，于是抄了一道原题给机房大佬过目：

给定一个长为n的排列A和一个不超过n的正整数k，求所有区间中第k大数的和。

机房大佬瞥了一眼，连道：“一眼题！”“傻X题！”

小W非常受伤，于是他把这个问题交给了你。

Format

Input

第一行输入两个整数，分别表示n和k。

接下来一行，输入n个整数，表示排列A。

Output

输出一行一个整数，表示所求的答案。

Samples

3 2
1 3 2

5

Limitation

【输入输出样例解释】

区间[1,1],[2,2],[3,3]没有第2大数，区间[1,2]的第2大数为1，区间[2,3]的第2大数为2，区间[1,3]的第2大数为2，所以答案为1+2+2=5。

【数据规模与约定】

对于20%的测试点：1≤k≤n≤200。

对于50%的测试点：1≤k≤n≤2,000。

对于80%的测试点：1≤k≤n≤200,000。

对于100%的测试点：1≤k≤n≤2,000,000,1≤n*k≤20,000,000。

其中在第三和第四档测试点中，各有占本题总分10%的测试点满足k=1。