‎$n$‎ جعبه الماس داریم که در جعبه ‎$i$‎ام ‎$i$‎ قطعه الماس وجود دارد که وزن هر کدام از آنها برابر است با ‎$w_i$.

می‌خواهیم تعدادی از این الماس‌ها را برداریم به طوری که وزن آن‌ها بیشینه شود اما وزن آنها از ‎$k$‎ بیش‌تر نشود. شما باید برنامه‌ای بنویسید تا بیش‌ترین وزنی از الماس‌ها را که می‌توانیم برداریم را به دست آورد.

• در سطر اول ورودی ‎$1 \leq n \leq 13$‎ و ‎$0 \leq k \leq 10^{15}$‎ آمده است.
• در سطر بعدی، ‎n‎ عدد آمده است که عدد ‎$i$‎ام نشانگر ‎$w_i$‎ است. تمامی اعداد داده شده بین ‎0‎ و ‎$10^{15}$‎ است.

در تنها سطر خروجی پاسخ سوال را بنویسید.‎

• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل