Taeyeon的困惑
题号:NC21788
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

今天,YPC正在热舞之中,嘴里唱着BJLY的神曲,沉浸在了自己的世界里。 然而Taeyeon又突然抽了一下,问YPC一个问题: 在一个长度为n的区间中,子区间[1,m],[2,m+1],[3,m+2],...,[n-m+1,n]中每个区间前K小之和的和是多少。

其中一个区间的前k小之和指的是将这个区间内的所有数从小到大排序后求出最前面的k个数之和

由于YPC热舞的起劲,无法自拔,于是这个问题只能你来回答。

输入描述:

第一行三个整数:n,m,K,意思如题 第二行n个正整数:a[i],意思如题

输出描述:

输出仅一行,每个区间前K小的数之和的和。
示例1

输入

复制
6 3 2
2 3 1 4 5 6

输出

复制
21

说明

对于30%数据:1≤n,m≤1000,0≤k≤m≤n,0≤a[i]≤105,m接近于n/2
对于100%数据:1≤n,m≤105,0≤k≤m≤n,0≤a[i]≤105,m接近于n/2。
保证数据纯随机
示例2

输入

复制
6 3 2
2 2 2 2 2 2

输出

复制
16