明知山有虎，偏向虎山行（雾

虽然知道正解是背包，但是仍然写了一个$sb$模拟退火（结果$\texttt{WA}$了一片

求救！！！

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <ctime>

using namespace std;

const int N = 60;

int cnt, path[N];
int res = -0x3f3f3f3f;
bool st[N];
int n, m, k1[N], k2[N], cost[N];

bool check()
{
	int used = 0;
	
	for (int i = 1; i <= cnt; i ++ )
		used += cost[path[i]];
		
	return used <= m;
}

int calc()
{
	int sum = 0, t = 0;
	
	for (int i = 1; i <= cnt; i ++ )
		t += cost[path[i]], sum += k1[path[i]] - t * k2[path[i]];
		
	res = max(res, sum);
	
	return sum;
}

void anneal_simulate()
{
	for (double t = 100000; t >= 1e-4; t *= 0.99)
	{
		int x = calc();
		int a = rand() % n;
		
		while (st[a])
			a = rand() % n;
			
		path[ ++ cnt] = a;
		
		if (!check())
		{
			cnt -- ;
			continue;
		}
		
		st[a] = true;
		int y = calc();
		
		int delta = y - x;
		if (exp(delta / t) > (double)rand() / RAND_MAX) cnt -- , st[a] = false;
	}
}

int main()
{
	scanf("%d%d", &m, &n);
	
	for (int i = 0; i < n; i ++ )
		scanf("%d", &k1[i]);
		
	for (int i = 0; i < n; i ++ )
		scanf("%d", &k2[i]);
		
	for (int i = 0; i < n; i ++ )
		scanf("%d", &cost[i]);
		
	while ((double)clock() / CLOCKS_PER_SEC < 0.8) memset(st, 0, sizeof st), cnt = 0, anneal_simulate();
	
	printf("%d\n", res);
	
	return 0;
}