W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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.
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.
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ą .
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.