• محدودیت زمان: ۰.۵ ثانیه
• محدودیت حافظه: ۱۲۸ مگابایت
• منبع: amppz 2012

اصغر پرنده به یک عروسی دعوت شده است. در هنگام شام $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

ابتدا از غذای ۱ تا ۶ می‌‌رویم و در طول راه از غذاهای نوع ۱، ۲، ۴، ۵ و ۶ هرکدام یک واحد برمی‌داریم (از غذای نوع ۳ نمی‌‌توان برداشت چون تعدادش ۰ است).

در مرحله بعد از غذای ۱ تا ۴ می‌رویم غذا های نوع ۲ و ۴ را برمی‌داریم.

در مرحله اول ۲ دلار و در مرحله دوم ۵ دلار هزینه کرده ایم که از پولمان که برابر با ۸ است کمتر است.

مجموع قیمت غذاها در مرحله اول برابر با ۲۳ و در مرحله دوم برابر با ۷ است.