## 978G-Petya's Exam

This is a greedy problem. First thing to notice is that exam which is occurring earlier compared to others should be prepared first, i.e. exam which is having less

*d*_{i}should be prepared earlier(if value of*s*allows to do so).Sort the exams in the increasing order of

*d*_{i}. If we go through solution we can see that it gives optimum solution.Let us take an exam from the sorted order = {

*s*_{i},*d*_{i},*c*_{i}}. Since we have sorted exams , 1 ≤*j*≤*n*AND*j*≠*i*; either*d*_{i}≤*d*_{j}or*j*^{th}exam is completed(We are processing in increasing order of*d*_{i}). Now we have to prepare*c*_{i}days for exam*i*in the interval*s*_{i}and*d*_{i}(and obviously we are forced to do so, so that's an optimal step). Now since all other exams(for which preparation is not done yet) are after*i*^{th}exam,**what is the best way to choose**?If we iterate from*c*_{i}days in the interval [*s*_{i},*d*_{i}] such that we leave better opportunities for the preparation of other exams*s*_{i}to*d*_{i}and choose first*c*_{i}days which are free for preparation. Hence our solution is optimal.Worst case time complexity is : O(m*n).