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 |