Laiko ribojimas: 3s

Atminties ribojimas: 512MB

Jei norite pateikti savo sprendimą - prisijunkite.

Kuprinė

Duota kuprinė, į kurią telpa k (1\\leqk\\leq10^5) kilogramų daiktų. Taip pat duota n (1\\leqn\\leq10^3) daiktų. Kiekvienas daiktas turi savo svorį s_i ir vertę v_i. Jūs norite į kuprinę sutalpinti kuo vertingesnius daiktus. Kokia didžiausia vertė gali būti kuprinėje?

Pradiniai duomenys

Pirmoje eilutėje pateikti tarpais atskirti skaičiai n ir k. Antroje eilutėje pateikta n skaičių s_1,s_2,...,s_n. Trečioje eilutėje pateikta n skaičių v_1,v_2,...,v_n.

Rezultatai

Išveskite vieną skaičių - didžiausią daiktų, kurie telpa kuprinėje, verčių sumą,

Pavyzdys

Duomenys Rezultatai
4 10
4 8 5 3
5 12 8 1
13