Automat
Limit pamięci: 128 MB
W budynku uczelni, na której studiuje Bajtazar, stoi automat sprzedający batony.
W automacie dostępnych jest rodzajów batonów, ponumerowanych od do .
Batony poszczególnych rodzajów różnią się rozmiarem oraz smakiem, więc
ich ceny mogą być różne.
Niedawno Bajtazar odkrył, że automat jest popsuty.
Kiedy kupi się jednego batona rodzaju , z automatu wypada także po jednym
batonie każdego z rodzajów , , ..., .
Oczywiście tylko wtedy, gdy batony tych rodzajów są dostępne -
jeśli batonów któregoś rodzaju między a nie ma w automacie,
baton tego rodzaju nie wypada.
Trzeba dodać, że ta sprytna sztuczka jest możliwa do wykonania tylko wtedy,
gdy w automacie faktycznie znajduje się co najmniej jeden baton -tego rodzaju.
Bajtazar postanowił zrobić użytek z wykrytej usterki.
Dysponując pewną kwotą pieniędzy, chciałby stwierdzić, jaką największą
wartość (tj. sumę cen) łakoci może wydobyć z automatu za tę kwotę.
Bajtazar nie musi zużyć całej dostępnej kwoty.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite oraz (, ),
oznaczające liczbę rodzajów batonów w automacie oraz kwotę, jaką dysponuje Bajtazar.
Drugi wiersz zawiera liczb całkowitych
(), oznaczających ceny batonów poszczególnych rodzajów.
Trzeci wiersz zawiera liczb całkowitych
(), oznaczających liczby batonów poszczególnych rodzajów dostępnych w automacie.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą -
sumę cen łakoci, jakie Bajtazar może nabyć w automacie, dysponując kwotą .
Przykład
Dla danych wejściowych:
6 8
7 2 3 5 7 2
1 3 0 3 2 1
poprawną odpowiedzią jest:
30
Wyjaśnienie do przykładu:
Kupujemy batona rodzaju 6, a z automatu wypada nam także
po jednym batonie rodzajów 1, 2, 4 i 5.
Kupujemy batona rodzaju 4, z automatu oprócz niego wypada
baton rodzaju 2.
Autor zadania: Jakub Pachocki.