POI阴影又发作了

但这道题挺好的，比较涨知识

裸的想法是裸的每次二分图匹配，但显然会TLE

这里就要引入Hall定理：

二分图G中的两部分顶点组成的集合分别为X, Y, X={X1, X2, X3,X4,.........,Xm}, Y={y1, y2, y3, y4 ,.........,yn},

图G中有一组无公共点的边，一端恰好为组成X的点的充分必要条件是：

X中的任意k个点至少与Y中的k个点相邻。（1≤k≤m)

任意这个东西相当烦，不能穷举，也不知道底要取X集合中哪些点来判断，乍一看还是不怎么好弄

但是这个图很特殊，把人看做X集合，鞋看做Y集合

因为同一鞋号x的人连的鞋都是[x,x+d]，所以集合X中同一个鞋号里的人要么取要么都不取（全取比取部分一定更具代表性）

然后再看，鞋号为x+1的人连的鞋是[x+1,x+1+d]，会有[x+1,x+d]的点被鞋号为x+1的人重复连了

也就是人鞋号是连续的时候连接的鞋最少

显然，所取的鞋号为连续的更有代表性（更可能出现不满足的情况）

因此，我们必须对于任意一段连续鞋号[l,r]

满足sigma(xi) （i∈[l,r]) <=(r-l+1+d)*k

也就是 sigma(xi)<=(r-l+1)*k+d*k

即 sigma(xi-k)<=d*k

也就是我们只要找出当前最长连续子序列与d*k比较就可以了

由于要修改，所以我们用线段树来维护

好，到这里我又要说pascal的不幸了，TLE到死……实在懒得卡常数了，就交了c++的

1 type node=record 2        lm,rm,mm,s:int64; 3      end; 4  5 var tree:array[0..800010] of node; 6     n,m,k,d,i,x,y:longint; 7     t:int64; 8  9 function max(a,b:int64):int64;10   begin11     if a>b then exit(a) else exit(b);12   end;13 14 procedure work(i,l,r:longint);15   var m:longint;16   begin17     if l=r then18     begin19       tree[i].s:=tree[i].s+y;20       tree[i].lm:=tree[i].s;21       tree[i].rm:=tree[i].s;22       tree[i].mm:=tree[i].s;23     end24     else begin25       m:=(l+r) shr 1;26       if x<=m then work(i*2,l,m)27       else work(i*2+1,m+1,r);28       tree[i].lm:=max(tree[i*2].lm,tree[i*2].s+tree[i*2+1].lm);29       tree[i].rm:=max(tree[i*2+1].rm,tree[i*2+1].s+tree[i*2].rm);30       tree[i].mm:=max(tree[i*2].mm,tree[i*2+1].mm);31       tree[i].mm:=max(tree[i].mm,tree[i*2].rm+tree[i*2+1].lm);32       tree[i].s:=tree[i*2].s+tree[i*2+1].s;33     end;34   end;35 36 procedure build(i,l,r:longint);37   var m:longint;38   begin39     if l=r then40     begin41       tree[i].s:=-k;42       tree[i].lm:=-k;43       tree[i].rm:=-k;44       tree[i].mm:=-k;45     end46     else begin47       m:=(l+r) shr 1;48       build(i*2,l,m);49       build(i*2+1,m+1,r);50       tree[i].lm:=max(tree[i*2].lm,tree[i*2].s+tree[i*2+1].lm);51       tree[i].rm:=max(tree[i*2+1].rm,tree[i*2+1].s+tree[i*2].rm);52       tree[i].mm:=max(tree[i*2].mm,tree[i*2+1].mm);53       tree[i].mm:=max(tree[i].mm,tree[i*2].rm+tree[i*2+1].lm);54       tree[i].s:=tree[i*2].s+tree[i*2+1].s;55     end;56   end;57 58 begin59   readln(n,m,k,d);60   build(1,1,n);61   t:=int64(k)*int64(d);62   for i:=1 to m do63   begin64     readln(x,y);65     work(1,1,n);66     if tree[1].mm<=t then67       writeln('TAK')68     else writeln('NIE');69   end;70 end.71 72