Problem
King Flatlands Tochter wird einen schönen Prinzen heiraten.
Der Prinz will der Prinzessin den Schatz geben, aber er ist nicht sicher, welche Diamanten aus seiner Sammlung sind.
In einer Prinzenkollektion von n Diamanten, jeder mit einem Gewicht von w.
I und Kosten v
I♪
Der Prinz will die teuersten Diamanten geben, aber der König des Lippenstifts wird die Diamanten nicht mehr als R annehmen. Auf der anderen Seite wäre der Prinz gierig für den Rest seines Lebens, wenn er den Diamanten eine Summe von Gewicht weniger als L gab.
Helfen Sie dem Prinzen wählen Sie die meisten aggregierten Wert Diamanten, so dass das aggregierte Gewicht in [L, R] ist.
Eingabe:Die erste Zeile enthält die Anzahl n (1 À=n À=32), L und R (0 À=L À=R À=10
183)
Die folgenden n Linien beschreiben die Diamanten und enthalten zwei Zahlen - das Gewicht und die Kosten des betreffenden Diamanten (1 À wi, vi PO=10)
15)
Ausgangsdaten:Die erste Linie der Rücknahme sollte k enthalten, die Anzahl der Diamanten, die der Prinzessin gegeben werden.
Die zweite Linie sollte die Anzahl der begabten Diamanten enthalten.
Die Diamanten sind zwischen 1 und n numeriert, um die Eingabedaten einzugeben.
Wenn es nicht möglich ist, ein Geschenk von der Prinzessin zu zeichnen, dann setzen Sie 0 in die erste Zeile der Auszahlung.
Beispiele:| Eingangsdaten | Ausgangsdaten |
3 6 8
3 10
3
Artikel 2 | 1
2 |