====== Diamonds ====== ‎$n$‎ جعبه الماس داریم که در جعبه ‎$i$‎ام ‎$i$‎ قطعه الماس وجود دارد که وزن هر کدام از آنها برابر است با ‎$w_i$. می‌خواهیم تعدادی از این الماس‌ها را برداریم به طوری که وزن آن‌ها بیشینه شود اما وزن آنها از ‎$k$‎ بیش‌تر نشود. شما باید برنامه‌ای بنویسید تا بیش‌ترین وزنی از الماس‌ها را که می‌توانیم برداریم را به دست آورد. ===== ورودی ===== * در سطر اول ورودی ‎$1 \leq n \leq 13$‎ و ‎$0 \leq k \leq 10^{15}$‎ آمده است. * در سطر بعدی، ‎n‎ عدد آمده است که عدد ‎$i$‎ام نشانگر ‎$w_i$‎ است. تمامی اعداد داده شده بین ‎0‎ و ‎$10^{15}$‎ است. ===== خروجی ===== در تنها سطر خروجی پاسخ سوال را بنویسید.‎ ===== محدودیت‌ها ===== * محدودیت زمان: ۳ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |3 10\\ 1 2 3 | 10 | |3 10 \\ 1 1 1 | 6 | |3 100 \\ 101 101 101 | 0 | * [[سوال ۱۵|سوال بعد]] * [[سوال ۱۳|سوال قبل]]