{"raw_statement":[{"iden":"statement","content":"The little mascot of the Shitalian mafia, Mafianca, is participating in her school's science fair. Her team must build a timeline with interesting events of the history of the universe.\n\nMafianca has been researching on the internet and managed to hack a NASA subdomain that has a list of N interesting cosmic events. The i-th event has the date Di and an interest value of Vi given by the scientists of NASA.\n\nMafianca wanted to use all events in the list, but she soon discovered they are not ordered by date. Also, the events are presented in a special manner and she can't change their order. She must choose some events to use, maximising the sum of their interest values. Her only restriction is that in her final timeline the events are not too distant time wise from each other.\n\nMafianca defined, for every event i, a value Ti. This value is the tolerance of the difference between the ages of this event and the previous event in the timeline. In other words, in case the event X shows up in the timeline, and the event immediately before is Y, DX - DY ≤ TX must hold true. Any event can be chosen as the starting one.\n\nHelp Mafianca build the best list possible.\n\nInput begins with an integer, n (1 ≤ n ≤ 105), the number of events. n line sfollow, each with three integers: Di (1 ≤ Di ≤ 1018), Vi (0 ≤ Vi ≤ 105) and Ti (1 ≤ Ti ≤ 106), representing the date, interest value and tolerance of the i-th event.\n\nPrint the interest value of the best list Mafianca can build.\n\n"},{"iden":"input","content":"Input begins with an integer, n (1 ≤ n ≤ 105), the number of events. n line sfollow, each with three integers: Di (1 ≤ Di ≤ 1018), Vi (0 ≤ Vi ≤ 105) and Ti (1 ≤ Ti ≤ 106), representing the date, interest value and tolerance of the i-th event."},{"iden":"output","content":"Print the interest value of the best list Mafianca can build."},{"iden":"examples","content":"Input31 2 13 1 12 2 3Output4Input31 2 13 3 13 2 2Output5Input56 1 33 1 312 1 65 1 217 1 8Output3Input61 1 12 1 13 2 11 2 12 2 13 2 1Output7"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s \\in \\Sigma^n $ be a string of length $ n $, where $ \\Sigma $ is a finite alphabet.  \nLet $ Q \\in \\mathbb{Z}^+ $ be the number of queries.  \nFor each query $ q \\in \\{1, \\dots, Q\\} $, let $ L_q \\in \\mathbb{Z}^+ $ and $ K_q \\in \\mathbb{Z}^+ $ be given parameters.\n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $  \n2. $ 1 \\le Q \\le 10^5 $  \n3. For each query $ q $:  \n   - $ 1 \\le L_q \\le n $  \n   - $ 1 \\le K_q \\le n - L_q + 1 $  \n\n**Objective**  \nFor each query $ q $, let $ W_q = \\{ s[i:i+L_q] \\mid i \\in \\{1, \\dots, n - L_q + 1\\} \\} $ be the multiset of all contiguous substrings of length $ L_q $.  \nSort $ W_q $ lexicographically to obtain a sequence $ W_q^{(1)} \\le W_q^{(2)} \\le \\dots \\le W_q^{(n - L_q + 1)} $.  \nOutput any index $ i \\in \\{1, \\dots, n - L_q + 1\\} $ such that $ s[i:i+L_q] = W_q^{(K_q)} $.","simple_statement":"Given a string of length n, for each query with L and K, find the starting position of any substring of length L that is the K-th lexicographically smallest substring of length L.","has_page_source":false}