Module: Muster in der dynamischen Programmierung

Problem

Interregionale Olympische Spiele zur Programmierung von Robotern werden in einer Tour und in einem ungewöhnlichen Format durchgeführt. Die Ziele der Teilnehmer werden immer und nicht alle zu Beginn der Tour gegeben, und jeder i-Task (1 ≤ (n) wird den Teilnehmern zum Zeitpunkt s_I♪ Nach Eingang einer weiteren Aufgabe muss jeder Teilnehmer sofort feststellen, ob er zufrieden ist oder nicht. Wenn er diese Aufgabe wählt, hat er t._I Minuten, um seine Entscheidung für die Überprüfung, und während dieser Zeit kann es nicht auf eine andere Aufgabe verschieben. Wenn sich der Teilnehmer dagegen weigert, dies zu tun, kann er zukünftig nicht zurückkommen. Am Ende der der Aufgabe zugewiesenen Zeit, die der Teilnehmer tut, kann es beginnen, eine andere Herausforderung zu erfüllen, die gleichzeitig zur Verfügung steht, wenn eine solche Aufgabe besteht, oder auf eine andere Herausforderung zu warten. Dabei erhält der Teilnehmer c_I Punkte.

Arthur, ein regionales Zentrum für künstliche Intelligenz in den interregionalen Olympischen Spielen, versteht, dass nicht nur die Fähigkeit, den Herausforderungen gerecht zu werden, sondern auch die richtige strategische Berechnung dessen, was angesprochen werden muss und was man vermissen muss, eine wichtige Rolle für ein solches Olympia ist. Er weiß, wie alle Teilnehmer, vor der Tour, zu welchem Zeitpunkt jede Aufgabe zur Verfügung stehen wird, wie viel Zeit ihr zugewiesen wird und wie viele Punkte für ihre Entscheidung erhalten werden können. Arthur ist ein talentierter Schüler und wird daher in der Lage sein, rechtzeitig zu lösen und jede Herausforderung zu testen, die er in den Olympischen Spielen lösen will.

Es ist notwendig, ein Programm zu schreiben, das die maximale Anzahl von Punkten bestimmt Arthur wird in der Lage sein, bei der optimalen Wahl der Aufgaben, die er übernehmen wird, sowie die Anzahl und Liste solcher Aufgaben zu erhalten.

Eingangsdaten
Die erste Zeile enthält eine ganze Zahl n (1 ≤ 10)^5.( Anzahl der Aufgaben bei Olympia.

Nachfolgende n Zeilen enthalten Beschreibungen der Aufgaben, dreimal jede Zeile: si den Moment, wenn die i Aufgabe in Minuten kommt, t_I Zugeteilte Zeit in Minuten und ci wie viele Punkte der Teilnehmer für diese Aufgabe erhalten (1 ≤ s)_I, t_I, c_I ≤ 10^ANHANG)

Ausgangsdaten
Die erste Zeile enthält eine Nummer, die maximale Anzahl von Punkten, die Arthur auf die Olympischen Spiele bekommen kann.

Die zweite Zeile sollte eine ganze m enthalten, die Anzahl der Aufgaben, die mit optimaler Wahl behandelt werden sollen.

Die dritte Zeile enthält m der Spaltlücken der ganzen Zahlen, die Nummern dieser Aufgaben, um sie zu adressieren. Die Aufgaben werden nummeriert, beginnend mit der Einheit, um sie in der Eingabedatei zu beschreiben.

Wenn die besten Antworten mehrere sind, muss man entweder entfernt werden.

Beispiele

Nein	Eingangsdaten	Ausgangsdaten
1	2 1 1 1 1 2 2 2	3 2 Artikel 2
2	3 1 2 1 3 2 1 Artikel 2	3 1 3