悬一关

code

#include<bits/stdc++.h>
using namespace std;
int n,d,need;
int cnt = 1008600;
int v[100005];
int a[100005];
void dfs(int oil,int cost,int step)
{
	if(cost >= cnt) return; 
	if(oil >= need)
	{
		cnt = min(cnt,cost);
		return;
	}
	if(oil * d < step) return;
	int cntt = 0;
	int k = 1;
	for(int i = 1;i <=n;i++)
	{
		if(step > cntt) k++,cntt+=v[i];
	}
	for(int i = 0;i <= need - oil;i++)
	{
		dfs(oil + i,cost + a[k] * i,step + v[k]);
	}
	return;
}
int main()
{
	cin >> n >> d;
	for(int i = 1;i <= n - 1;i++) scanf("%d",&v[i]),need += v[i];
	for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
	if(need % d == 0) need /= d;
	else need = need / d + 1;
	dfs(0,0,0);
	cout << cnt;
	return 0;
}
/*
5 4
10 10 10 10
9 8 9 6 5
*/