Problem
Sie arbeiten als Manager und erstellen einen Arbeitsplan für den nächsten Monat. Jeder Monat ist in T gleiche Zeiteinheiten unterteilt. Es gibt insgesamt n Aufgaben, die erledigt werden müssen. Sie verstehen jedoch, dass Sie möglicherweise keine Zeit haben, alle Aufgaben in einem Monat zu erledigen, und Sie möchten einen optimalen Plan erstellen, indem Sie einige von ihnen auswählen.
Jede Aufgabe kennt die Zeit ti, die Sie aufwenden müssen, um sie zu erledigen, sowie den Gewinn pi, den die gemachte Aufgabe dem Unternehmen bringen wird. Sie möchten einige Aufgaben in den Plan aufnehmen, so dass:
- Die Gesamtzeit, die für die Ausführung der im Plan enthaltenen Aufgaben aufgewendet wurde, hat
T nicht überschritten.
- Der Gesamtgewinn aus diesen Aufgaben war maximal.
Erstellen Sie einen Plan mit den oben beschriebenen Eigenschaften und bestimmen Sie den Gewinn, der durch die Ausführung dieses Plans erzielt wird.
Beachten Sie, dass der einzige Plan, der für die Bedingungen geeignet ist, möglicherweise keine Aufgabe enthält.
Eingabedaten
Die erste Zeile enthält natürliche Zahlen T (1 ≤ T ≤ 100 000) und n (1 ≤ n ≤ 10) - die Anzahl der Zeiteinheiten pro Monat und die Anzahl der Aufgaben.
Die folgenden n Strings enthalten jeweils zwei natürliche Zahlen ti und pi (1<= ti, pi <= 100 000) - Die Zeit, die für die Ausführung von i benötigt wird, ist die Zeit, die für die Ausführung von i benötigt wird.i und pi (1<= ti, pi <= 100 000). aufgaben und Gewinne, die durch das Ausführen erzielt werden können.
Ausgabe Daten
Geben Sie die Einzelzahl aus, — der maximale Gewinn, den Sie erzielen können, indem Sie einen Plan erstellen, der den oben beschriebenen Bedingungen entspricht.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
10 3
8 100
3 10
3 10 |
100 |
| 2 |
10 4
5 10
5 20
2 5
2 6 |
31 |