Šeštadieninė informatikos olimpiadininkų mokykla

Vagis, naktį įsilaužęs į muziejų, rado n vertingų eksponatų. Žinoma kiekvieno eksponato vertė vk bei svoris sk, išreikšti sveikaisiais skaičiais. Vagis gali panešti kuprinę, sveriančią ne daugiau kaip S kilogramų.

Užduotis

Reikia nustatyti, kuriuos eksponatus jis turėtų susikrauti į kuprinę, kad bendra jų vertė būtų kuo didesnė, o kuprinė – panešama.

Pradiniai duomenys

Pirmoje eilutėje duoti daiktų kiekis () ir didžiausias svoris (), kurį vagis gali panešti . Tolesnėse eilutėse nurodyti daiktai, kuriuos apibūdina du skaičiai - tai daikto vertė ir daikto svoris, šie dydžiai yra nedidesni nei 1000.

Pavyzdys

5 12
1 1
5 2
8 3
11 4
20 7

33