Problem
フラットランドの王の娘がチャーミング王子と結婚しようとしています。
王子は王女に宝物をあげたいと思っていますが、コレクションからどのダイヤモンドを選べばよいかわかりません。
王子のコレクションには n 個のダイヤモンドがあり、それぞれの重さ w
i と値 v
i で特徴付けられています。
王子は最も高価なダイヤモンドを贈りたいと考えていますが、王様は頭が良く、総重量が R を超えるダイヤモンドを受け入れません。総重量がL未満。
合計重量がセグメント [L, R] に収まるように、王子が合計値が最も高いダイヤモンドのセットを選択するのを手伝ってください。
入力:
最初の行には、数値 n (1 <= n <= 32)、L および R (0 <= L <= R <= 10
18) が含まれます。
次の n 行はダイヤモンドを説明し、それぞれ 2 つの数値 (対応するダイヤモンドの重量と値) を含みます (1 <= wi, vi <= 10
15)。
出力:
出力の最初の行には、王女に贈るダイヤモンドの数である k が含まれている必要があります。
2 行目には、与えられるダイヤモンドの数が含まれている必要があります。
ダイヤモンドには、入力に現れる順序で 1 から n までの番号が付けられます。
王女へのプレゼントを作成できない場合は、出力の最初の行に 0 を出力します。
例:
<本体>
| 入力 |
出力 |
3 6 8
3 10
7 3
8 2 |
1
2 |