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