餐厅排队取餐策略：优化顾客等待时间，最大化餐厅评分

有 'n' 个人在排队取餐。每个人都有自己的口味偏好，他们会在手机上自助选择好自己想要的餐品。不同的餐品需要不同的制作时间。

你是这家餐厅的老板，作为生意火爆的网红打卡点，你的餐厅营业时间一天只有 'm' 分钟。如果某个顾客能够吃到他点的餐品，他会就给餐厅打分。第 'i' 个人如果吃到了餐品，他就会给餐厅打 'x[i]' 分。但是由于不能马上吃到餐品，顾客就会产生不满。如果第 'i' 个人吃到餐品等待了 'q' 分钟，他就会减少打分，分数就会减少 'q * y[i]'，这里 'y[i]' 表示顾客每分钟产生的不满度。并且每个顾客有一个等待爆发周期 'z[i]'，即每隔 'z[i]' 分钟会直接降低打分 30 分。当然，只要顾客吃到了餐品，他至少会给餐厅打原本分数的一半。

作为老板，你当然是可以看到所有顾客的要求的。为了让你的餐厅的总分尽量高，你决定调整出餐的顺序。请你根据给出的顾客要求，来安排出餐顺序获得最高的总分。当然不一定每位顾客都能在营业时间内获得餐品。

输入格式

第一行输入两个数 'n, m'，表示共有 'n' 个人，营业时间为 'm' 分钟

接下来输入 'n' 行，每行输入四个数 'x[i], y[i], z[i], t[i]'。'x[i]' 表示第 'i' 个顾客如果吃到餐品会打的最高分数，'y[i]' 表示每分钟产生的不满度，'z[i]' 表示等待爆发周期，每个周期减少 30 分。't[i]' 表示制作该餐品所需要花费的时间。

输出格式

输出一行一个数，表示获得的最高总分。

输入样例

2 100
1000 4 30 50
500  2 50 50

输出样例

数据范围

对于 70% 的数据，保证 'n ≤ 10' 对于 100% 的数据，保证 'n ≤ 20, m ≤ 1000, 1 ≤ x[i] ≤ 10000, 0 ≤ y[i] ≤ 100, 1 ≤ z[i] ≤ 100, 1 ≤ t[i] ≤ 100' 每个顾客初始的最高分数保证是 10 的倍数。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20,M = 1010;
int n,m;
struct node{
    int x,y,z,t;
}a[N];
int f[N][M];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y>>a[i].z>>a[i].t;
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=a[i].t;j--)
        {
            for(int k=0;k<a[i].z;k++) // 周期
            {
                if(j-k-a[i].t>=0) 
                    f[i][j] = max(f[i][j],f[i-1][j-k-a[i].t]+a[i].x-max(0,(k+1)*a[i].y)); // 注意这里是i-1
                ans = max(ans,f[i][j]+max(a[i].x/2,-(j-a[i].t)*a[i].y)); // 注意这里是f[i][j]
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}