$n$ جعبه الماس داریم که در جعبه $i$ام $i$ قطعه الماس وجود دارد که وزن هر کدام از آنها برابر است با $w_i$.
میخواهیم تعدادی از این الماسها را برداریم به طوری که وزن آنها بیشینه شود اما وزن آنها از $k$ بیشتر نشود. شما باید برنامهای بنویسید تا بیشترین وزنی از الماسها را که میتوانیم برداریم را به دست آورد.
در تنها سطر خروجی پاسخ سوال را بنویسید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 3 10 1 2 3 | 10 |
| 3 10 1 1 1 | 6 |
| 3 100 101 101 101 | 0 |