A city is presented as a segment with O is the start and length is t (t<=1e9). On that segment there are n lamppost from 1 to n which can presented by xi,hi,pi where xi is the distance from O to to the lamppost, hi is the height of the lampppost, pi is the price of using this lamppost. If the lampost is turn on, it can light all point in [x[i]-h[i];x[i]+h[i]]. It is sure that if we turn on all the light every point on the road will be lighted by at least 2 lammposts. But the government want to save the money as much as possible so they decide that they will turn off some lampposts so that every point on the road are still be lighted by at least 2 lamppposts . Find that value and print out the light that you will turn on .

Input first n , t ; n line after x[i] , h[i] ,p[i] , position of lamppost , height of lammpost , price of lamppost

Output first line : print out the minimum price second line : print out the indexes of the lights you have chosen . constraint n<=2000 , t<=1e9 ; 0<=x[i]<=t,1<=h[i] ,p[i]<=1e9 ;

Can any one give me any idea . I try to use maximum flow but I can't

given a bipartite graph we call L as the left one and R as the right one for each node i we choose in L we have to pay a[i] dollar . there are m edges L[i] and R[j] m <= (|L|*|R|) ask : what is the minumum value of choose some node in L so that every node in R have at least 2 node in L is linked to this is chosen p/s sorry for my poor Engligh but if you understand the statement please give feedback

hello every my name is nguyentrongvanviet a student in Viet Nam (sorry for my poor English but please give me advice if you can) I want to be better at cp to get a better university in my country but to do that I have to get a degree or a certificate at cp contest such as VOI or ICPC ( in my country)

I am very interested at some new topic at the first day such as ST ,BIT ,DSU , DFS , BFS , graph :( but after a while I found other topic such as super DP problem or some super difficult adhoc problem :( (as I think) but after have seen the answer from teacher or some other guy I find it not that difficult but there are so many times I get into this situtation, I has a special ability that I can digest something new pretty fast but I don't know where to start even have started already is there any idea that I can follow (I am not a very good person who can make plan ) so please give me your idea if you can