题目描述

给定 $n$ 行 $m$ 列的矩阵，每一列的所有数数值相同，要求从第一列的某个数选起选出 $k$ 个数。每次在上一个数的基础上向上下左右四个方向移动，在某一列的第一行向上移动可到达该列的最后一行。被选过的数不可重复选取，求选出的数的最大和。

输入格式

第一行三个数 $n,m,k$ 含义如题。

接下来 $m$ 个数表示矩阵的第一行。

输出格式

输出一行一个数表示最大和。

样例

输入样例

1 5 3
1 2 3 4 5

输出样例

6

数据范围与提示

对于 $20\%$ 的数据，$1 \le k \le 12$。

对于 $70\%$ 的数据，$1 \le n,m \le 1000$。

对于 $100\%$ 的数据，$1 \le n,m \le 10^6$，$1 \le k \le nm$，数值在 $10^6$ 以内。

---

die码：

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define eb emplace_back
#define mkp(x,y) make_pair((x),(y))
#define pii pair<int,int>
#define fi first
#define se second
#define fir first
#define sec second
#define il inline
#define re register
#define maxn 1111111
//#define mp(x,y) make_pair((x),(y))
//#define int long long
using namespace std;
struct node{
	ll val;
};
bool operator<(node x,node y){
	return x.val>y.val;
}
ll n,m,K;
priority_queue<node> q;
signed main(){
	scanf("%lld%lld%lld",&n,&m,&K);
	ll ans=0,sum=0,cnt=0,mx=0;
	for(ll i=1;i<=m;++i){
		node x;
		scanf("%lld",&x.val);
		q.push(x);
		cnt+=n;sum+=n*x.val;
		while(cnt>K&&q.size()){
			node t=q.top();
			q.pop();
			cnt-=n-1;
			sum-=(n-1)*t.val;
			mx=t.val;
		}
		ans=max(ans,sum+min(n,K-cnt)*mx);
	}
	printf("%lld",ans);
	return 0;
}