考虑离线，将物品和询问都按a从小到大排序。

然后对于当前处理的询问，将所有a不超过它的物品都加入背包中。

设f[i]表示和为i时min(b)的最大值，若f[k]>m+s，则TAK。

时间复杂度$O(q\log q+nk)$。

 

#include
     
      #include
      
       const int N=1000010,M=100000;int n,m,i,j,k,f[M+1];bool ans[N];struct P{int a,b,c,p;}a[1010],b[N];inline bool cmp(P a,P b){return a.a
       
        ='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}int main(){  for(read(n),i=1;i<=n;i++)read(a[i].c),read(a[i].a),read(a[i].b);  for(read(m),i=1;i<=m;i++)read(b[i].a),read(b[i].c),read(b[i].b),b[i].b+=b[i].a,b[i].p=i;  for(std::sort(a+1,a+n+1,cmp),std::sort(b+1,b+m+1,cmp),f[0]=2000000001,i=j=1;i<=m;i++){    for(;j<=n&&a[j].a<=b[i].a;j++)for(k=M;k>=a[j].c;k--)up(f[k],min(f[k-a[j].c],a[j].b));    ans[b[i].p]=f[b[i].c]>b[i].b;  }  for(i=1;i<=m;i++)puts(ans[i]?"TAK":"NIE");  return 0;}