Problem
دختر پادشاه فلاتلند در آستانه ازدواج با شاهزاده چارمینگ است.
شاهزاده می خواهد گنجینه هایی را به شاهزاده خانم بدهد، اما مطمئن نیست که کدام الماس را از مجموعه خود انتخاب کند.
n الماس در مجموعه شاهزاده وجود دارد که هر کدام با وزن w
i و ارزش v
i مشخص می شوند.
شاهزاده می خواهد گران ترین الماس ها را بدهد اما پادشاه باهوش است و الماس هایی با وزن کل بیشتر از R را نمی پذیرد. از طرفی شاهزاده اگر الماس بدهد تا آخر عمر خود را حریص می داند. با وزن کل کمتر از L.
به شاهزاده کمک کنید مجموعه ای از الماس ها را با بالاترین ارزش کل انتخاب کند تا وزن کل در بخش [L, R] باشد.
ورودی:
خط اول شامل عدد n (1 <= n <= 32)، L و R (0 <= L <= R <= 10
18).
n خط بعدی الماس ها را توصیف می کند و هر کدام شامل دو عدد است - وزن و ارزش الماس مربوطه (1 <= wi, vi <= 10
15).
خروجی:
خط اول خروجی باید حاوی k باشد - تعداد الماس هایی که باید به شاهزاده خانم بدهید.
خط دوم باید شامل اعداد الماس هایی باشد که باید داده شوند.
الماس ها به ترتیبی که در ورودی ظاهر می شوند از 1 تا n شماره گذاری می شوند.
اگر نوشتن هدیه برای شاهزاده خانم غیرممکن است، 0 را در خط اول خروجی چاپ کنید.
مثال:
<بدن>
| ورودی |
خروجی |
3 6 8
3 10
7 3
8 2 |
1
2 |