Aufgaben und Deadlines
Du hast
n Aufgaben, jede mit einer bestimmten Deadline und einem Profit, den du erhältst, wenn du die Aufgabe rechtzeitig vor Ablauf ihrer Deadline fertigstellst. Jede Aufgabe dauert genau 1 Tag. Wenn du eine Aufgabe nicht rechtzeitig abschließt, erhältst du dafür keinen Profit.Du beginnst am Tag 1. Wie viel Profit kannst du insgesamt erzielen?
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ ), also die Anzahl der Aufgaben.Die nächsten
n Zeilen enthalten jeweils zwei durch Leerzeichen getrennte ganze Zahlen (1 ≤ , ≤ ). Dabei steht für die Deadline und für den Profit, den du erhältst, wenn du diese Aufgabe rechtzeitig erledigst.Ausgabe
Das Programm soll den maximalen Gesamtprofit ausgeben, den du erzielen kannst.
Beispiele
Eingabe | Ausgabe |
4
4 10
1 3
2 7
2 3 | 20 |
5
1 1
4 100
4 200
4 300
4 200 | 800 |
Erläuterung
- 10 + 3 + 7
- Zuerst erledigst du die Aufgabe mit Deadline 1 ⇒ Gewinn: 3
- Danach die Aufgabe mit Deadline 2 ⇒ Gewinn: 7
- Anschließend eine Aufgabe mit Deadline 4 ⇒ Gewinn: 10
- 100 + 200 + 300 + 200 (nur Aufgaben mit Deadline 4)
- Führe die Aufgabe mit einem Profit von 100 aus
- Als Nächstes die Aufgabe mit einem Profit von 200
- Danach die Aufgabe mit einem Profit von 300
- Und schließlich die Aufgabe mit einem Profit von 200
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB