* محدودیت زمان: ۰.۵ ثانیه * محدودیت حافظه: ۱۲۸ مگابایت ---------- **اصغر پرنده** به یک عروسی دعوت شده است. در هنگام شام $n$ نوع غذا روی میز قرار دارند که به ترتیب از ۱ تا $n$ شماره گذاری شده اند. خانواده داماد که بسیار خسیس هستند از مهمان ها بابت شام پول می‌‌گیرند. تعداد واحد های موجود از غذای $i$ام $L_{i}$، و قیمت هر واحد از آن برابر با $C_{i}$ است. هربار که یک مهمان بشقابی برمی‌‌دارد، باید از غذای شماره ۱ تا غذای شماره $p$ حرکت کند و یک واحد از هر غذایی که تمام نشده بود بردارد و در نهایت $C_{p}$ دلار پول بپردازد. این کار را در صورتی می‌توان انجام داد که از غذای $p$ام حداقل یک واحد موجود باشد. اصغر گشنه است، قیمت دلار بالا رفته و جمع پول هایی که در جیب و جورابش پنهان کرده روی هم $k$ دلار است. او می‌‌خواهد این پول را به طوری خرج کند که جمع قیمت غذاهایی که می‌‌خورد بیشینه شود. این مقدار بیشینه را به دست آورید. # ورودی در خط اول ورودی دو عدد $n$ و $k$ آمده اند. در خط دوم، $n$ عدد که $i$امین آنها $C_{i}$ است، و در خط بعدی هم $n$ عدد که $i$امین‌شان برابر با $L_{i}$ است آمده اند. $$1 \le n \le 40$$ $$1 \le k \le 64\ 000$$ $$1 \le C_{i} \le 40$$ $$0 \le L_{i} \le 40$$ # خروجی خروجی برنامه تنها یک عدد است که برابر با بیشینه مقدار مجموع قیمت غذاهاست. # زیرمسئله‎ها | زیرمسئله | نمره | محدودیت | |:-------:|:----------:|:-----------:| |۱| ۱۰۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ``` 6 8 7 2 3 5 7 2 1 3 0 3 2 1 ``` ## خروجی نمونه ``` 30 ``` ابتدا از غذای ۱ تا ۶ می‌‌رویم و در طول راه از غذاهای نوع ۱، ۲، ۴، ۵ و ۶ هرکدام یک واحد برمی‌داریم (از غذای نوع ۳ نمی‌‌توان برداشت چون تعدادش ۰ است). در مرحله بعد از غذای ۱ تا ۴ می‌رویم غذا های نوع ۲ و ۴ را برمی‌داریم. در مرحله اول ۲ دلار و در مرحله دوم ۵ دلار هزینه کرده ایم که از پولمان که برابر با ۸ است کمتر است. مجموع قیمت غذاها در مرحله اول برابر با ۲۳ و در مرحله دوم برابر با ۷ است.

حل سؤال در بانک سؤالات