Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ETI07E7 - Wiosna radosna

Wraz z nadejściem ciepłych, majowych dni Jaś i Staś postanowili wybrać się na majówkę. Lista potrzebnych przedmiotów jest bardzo długa, a plecaki, niestety, tylko dwa! Każdy przedmiot ma swoją wartość oraz rozmiar. Plecaki natomiast nie są workami bez dna i nie zmieszczą wszystkich rzeczy. Plecak Jasia ma rozmiar J, natomiast plecak Stasia ma rozmiar S. Zadaniem braci jest upakowanie w obu plecakach najbardziej wartościowego zestawu przedmiotów (każdy zabrany przedmiot zostaje umieszczony albo w plecaku Jasia, albo w plecaku Stasia).

Wejście

W pierwszym wierszu podane są trzy wartości całkowite oznaczające odpowiednio liczbę przedmiotów n (n <= 100), rozmiar plecaka Jasia J (J <= 500) oraz rozmiar plecaka Stasia S (S <= 500). W kolejnych n wierszach podane są pary liczb całkowitych o wartościach nie większych niż 100, oznaczające wartości i rozmiary przedmiotów.

Wyjście

W pierwszym wierszu należy podać możliwie największą łączną wartość wszystkich zapakowanych przedmiotów. W drugim wierszu należy wypisać numery wszystkich przedmiotów zapakowanych do pierwszego plecaka. W trzecim wierszu należy wypisać numery wszystkich przedmiotów zapakowanych do drugiego plecaka (w kolejności numerów z listy wejściowej).

Przykłady

Zestaw przykładowy 1

Wejście:
6 4 3
4 1
6 2
3 2
2 1
1 1
3 3

Wyjście:
16
1 2 4
3 5

Zestaw przykładowy 2

Wejście:

4 6 3
1 2
2 2
4 4
3 2

Wyjście:
9
3 4
2

Dodane przez:mima
Data dodania:2006-11-15
Limit czasu wykonania programu:1s-10s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.