这道题其实我在刚学 OI 的时候就在一本通上看见过，还记得上面写着“新餐巾一次性买完”之类的话。当时还很稚嫩（现在也是），想了好久，根本想不出来。

学了网络流之后发现这道题的图也是挺好构造的。 以

样例

3

1 7 5

11 2 2 3 1

为例：



先拆点。



每天都可以买最多 \(+\infty\) 张餐巾，单价为 \(p\)。给源点和所有的上半点连容量为 \(+\infty\)，费用为 \(p\) 的有向边。除此之外，每天的新餐巾也可以免费送到下一天，连上相应的有向边。



第 \(i\) 天需要 \(r_i\) 张餐巾，即第 \(i\) 天的上半点会向下半点流出 \(r_i\) 张脏餐巾，费用为 \(0\)。这里要稍作处理，让上半点的 \(d_i\) 张脏餐巾流往汇点；为了补偿下半点，允许源点往下半点流 \(d_i\) 张免费的脏餐巾。之所以这么做，是因为我们要求上午用去的餐巾数为 \(d_i\)，而不是要求下午不送洗的餐巾数为 \(d_i\)。



慢洗和快洗分别会向 \(m\) 天和 \(n\) 天后流出新餐巾，每天最多可以洗 \(+\infty\) 张，费用分别为 \(f\)，\(s\)。在这里慢洗部由于太慢，最终无法派上用场。

这张图的最大流最小费用就是答案。

#include <cstdio>

#include <cstring>

#include <queue>

inline int min(const int& a, const int& b){

	return a < b ? a : b;

}

const int MAXN = 4e3 + 19, MAXM = 8e4 + 19, INF = 0x3f3f3f3f;

struct Edge{

	int to, next, c, dist;

}edge[MAXM << 1];

int cnt = -1, head[MAXN];

inline void add(int from, int to, int c, int dist){

	edge[++cnt].to = to;

	edge[cnt].c = c;

	edge[cnt].dist = dist;

	edge[cnt].next = head[from];

	head[from] = cnt;

}

int N, p, m, f, n, s;

int dist[MAXN], flow[MAXN], pre[MAXN];

int spfa(void){

	std::queue<int>q; q.push(0);

	std::memset(dist, 0x3f, sizeof dist); dist[0] = 0;

	std::memset(flow, 0x3f, sizeof flow);

	while(!q.empty()){

		int node = q.front(); q.pop();

		for(int i = head[node]; i != -1; i = edge[i].next)

			if(edge[i].c && dist[edge[i].to] > dist[node] + edge[i].dist){

				dist[edge[i].to] = dist[node] + edge[i].dist;

				flow[edge[i].to] = min(flow[node], edge[i].c);

				pre[edge[i].to] = i;

				q.push(edge[i].to);

			}

	}

	if(flow[N + N + 1] == 0x3f3f3f3f)

		return 0;

	return flow[N + N + 1];

}

void edmondsKarp(long long& fee){

	while(spfa()){

		fee += (long long)flow[N + N + 1] * (long long)dist[N + N + 1];

		for(int i = N + N + 1; i; i = edge[pre[i] ^ 1].to)

			edge[pre[i]].c -= flow[N + N + 1], edge[pre[i] ^ 1].c += flow[N + N + 1];

	}

}

int main(){

	std::memset(head, -1, sizeof head);

	std::scanf("%d%d%d%d%d%d", &N, &p, &m, &f, &n, &s);

	for(int d, i = 1; i <= N; ++i){

		std::scanf("%d", &d);

		add(i, N + N + 1, d, 0), add(N + N + 1, i, 0, 0);

		add(0, i + N, d, 0), add(i + N, 0, 0, 0);

	}

	for(int i = 1; i <= N; ++i)

		add(0, i, INF, p), add(i, 0, 0, -p);

	for(int i = 1; i < N; ++i)

		add(i, i + 1, INF, 0), add(i + 1, i, 0, 0);

	for(int i = 1; i + m <= N; ++i)

		add(i + N, i + m, INF, f), add(i + m, i + N, 0, -f);

	for(int i = 1; i + n <= N; ++i)

		add(i + N, i + n, INF, s), add(i + n, i + N, 0, -s);

	long long ans = 0; edmondsKarp(ans);

	printf("%lld\n", ans);

	return 0;

}