Problem
Flatland Kralı'nın kızı Yakışıklı Prens ile evlenmek üzere.
Prens, prensese hazineler vermek istiyor ama koleksiyonundan hangi elmasları seçeceğinden emin değil.
Prensin koleksiyonunda her biri ağırlık w
i ve değer v
i ile karakterize edilen n adet elmas vardır.
Prens en pahalı elmasları vermek ister, ancak kral akıllıdır ve toplam ağırlığı R'den fazla olan elmasları kabul etmez. Öte yandan, prens elmas verirse hayatının geri kalanında kendini açgözlü olarak kabul eder. toplam ağırlığı L'den az olan.
Toplam ağırlığın [L, R] kesiminde olması için prensin en yüksek toplam değere sahip bir elmas seti seçmesine yardım edin.
Giriş:
İlk satır n (1 <= n <= 32), L ve R (0 <= L <= R <= 10
18) sayısını içerir.
Sonraki n satır elmasları tanımlar ve her biri iki sayı içerir - karşılık gelen elmasın ağırlığı ve değeri (1 <= wi, vi <= 10
15).
Çıktı:
Çıktının ilk satırı, k - prensese verilecek elmas sayısını içermelidir.
İkinci satır ise verilecek elmasların numaralarını içermelidir.
Elmaslar girişte göründükleri sırayla 1'den n'ye kadar numaralandırılır.
Prenses için bir hediye oluşturmak imkansızsa çıktının ilk satırına 0 yazın.
Örnekler:
| Giriş |
Çıktı |
3 6 8
3 10
7 3
8 2 |
1
2 |