神经做法，dalao请进

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

虽然知道正解是背包，但是仍然写了一个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;
}