#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 6005;
int n,maxL,T;
int s[MAXN], h[MAXN], p[MAXN], ramas[MAXN];
pair<int, vector<pair<pair<int,int>,int>>> calc(int L)
{
vector<int> ord;
for(int i=1;i<=n;i++)
ord.push_back(i);
sort(ord.begin(), ord.end(), [&](int x, int y)
{
if(s[x] != s[y])
return s[x] < s[y];
return p[x] > p[y];
});
for(int i=1;i<=n;i++)
ramas[i] = h[i] * L;
priority_queue<pair<int,int>> pq;
int curt = 0;
s[n+1] = T;
ord.push_back(n+1);
vector<pair<pair<int,int>,int>> timeline;
for(int id:ord)
{
//cerr<<id<<": "<<s[id]<<" "<<h[id]*L<<" "<<p[id]<<"\n";
while(!pq.empty() && curt + ramas[pq.top().second] <= s[id])
{
timeline.push_back({{curt, curt + ramas[pq.top().second]}, pq.top().second});
curt += ramas[pq.top().second];
ramas[pq.top().second] = 0;
pq.pop();
}
if(!pq.empty())
{
assert(curt + ramas[pq.top().second] > s[id]);
timeline.push_back({{curt, s[id]}, pq.top().second});
ramas[pq.top().second] -= s[id] - curt;
curt = s[id];
}
curt = s[id];
pq.push({p[id], id});
}
vector<pair<pair<int,int>,int>> newt;
if(!timeline.empty())
{
newt.push_back(timeline[0]);
for(int i=1;i<timeline.size();i++)
{
if(newt.back().second == timeline[i].second)
{
assert(newt.back().first.second == timeline[i].first.first);
newt.back().first.second = timeline[i].first.second;
}
else
{
newt.push_back(timeline[i]);
}
}
}
timeline = newt;
int rez = 0;
for(int i=1;i<=n;i++)
rez += ramas[i] * p[i];
//cerr<<L<<" "<<rez<<" cost\n\n";
return {rez, timeline};
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>maxL>>T;
for(int i=1;i<=n;i++)
{
cin>>s[i]>>h[i]>>p[i];
}
int curL = 0, curcost = -1, curdif = 0, first_bad = 1;
int q;
cin>>q;
while(q--)
{
int m;
cin>>m;
while(curL+1 <= maxL+1 && curcost <= m)
{
curL++;
if(curL == first_bad)
{
vector<pair<pair<int,int>,int>> oldt, newt, newt2;
tie(curcost, oldt) = calc(curL);
int newcost;
tie(newcost, newt) = calc(curL + 1);
curdif = newcost - curcost;
int cost2;
tie(cost2, newt2) = calc(curL + 2);
//cerr<<curcost<<" "<<newcost<<" "<<cost2<<" cost progression\n";
first_bad = maxL + 3;
if(newt.size() != oldt.size())
first_bad = 1;
else
{
for(int i=0;i<oldt.size();i++)
{
if(oldt[i].second != newt[i].second)
{
first_bad = 1;
break;
}
int oldlun = oldt[i].first.second - oldt[i].first.first;
int newlun = newt[i].first.second - newt[i].first.first;
int newlun2 = newt2[i].first.second - newt2[i].first.first;
cerr<<oldlun<<" vs "<<newlun<<" vs "<<newlun2<<" luns\n";
if(newlun < oldlun)
{
first_bad = min(first_bad, (oldlun - 1) / (oldlun - newlun) + 1);
//cerr<<"upd luns\n";
}
}
if(first_bad != 1)
{
for(int i=0;i+1<oldt.size();i++)
{
int olddist = oldt[i+1].first.first - oldt[i].first.second;
int newdist = newt[i+1].first.first - newt[i].first.second;
int dist2 = newt2[i+1].first.first - newt2[i].first.second;
cerr<<olddist<<" vs "<<newdist<<" vs "<<dist2<<" dists\n";
if(newdist < olddist)
{
first_bad = min(first_bad, (olddist - 1) / (olddist - newdist) + 1);
//cerr<<"upd dists\n";
}
}
}
}
cerr<<first_bad<<" after how many steps recalc\n\n";
assert(first_bad > 0);
first_bad += curL;
}
else
curcost += curdif;
}
cout<<curL-1<<"\n";
}
return 0;
}
