H. Precise Shopping

Codeforces

IDCF10113H

Time6000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

When Baklazan goes shopping, he likes calculating how much he should pay and prepare that amount exactly. There are n coins in his wallet, numbered 1 through n. Coin i has denomination di. Also, each coin is somewhat interesting to Baklazan; coin i has the interestingness of ai. This time, Baklazan forgot the first step — he doesn't know the exact amount of money to pay. He only remembers that it won't exceed b. Therefore, he'd like to prepare a subset S of his coins such that there's a subset of S with the sum of denominations equal to k for every k between 1 and b, inclusive. Of course, it's better not to give away interesting coins. Therefore, if there are multiple ways to choose S, he'd like to minimise the sum of interestingnesses of coins in S. Note that it's not necessary to minimise the size of S. The first line of the input contains two integers n and b (1 ≤ n ≤ 42, 1 ≤ b ≤ 109). The i-th of the next n lines contains two integers di and ai (1 ≤ di, ai ≤ 109) — the denomination and the interestingness of the i-th coin. If it's impossible to choose a suitable subset S, print "_-1_" (without the quotes) on a single line. Otherwise, print two lines. On the first line, print one integer denoting the size of your chosen subset S. On the second line, print the space-separated indices of chosen coins. You may print the indices in any order. If there are multiple ways to choose an optimal S, you may print any of them. ## Input The first line of the input contains two integers n and b (1 ≤ n ≤ 42, 1 ≤ b ≤ 109).The i-th of the next n lines contains two integers di and ai (1 ≤ di, ai ≤ 109) — the denomination and the interestingness of the i-th coin. ## Output If it's impossible to choose a suitable subset S, print "_-1_" (without the quotes) on a single line.Otherwise, print two lines. On the first line, print one integer denoting the size of your chosen subset S. On the second line, print the space-separated indices of chosen coins. You may print the indices in any order. If there are multiple ways to choose an optimal S, you may print any of them. [samples]

**Definitions** Let $ n, b \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 42 $, $ 1 \leq b \leq 10^9 $. Let $ C = \{ (d_i, a_i) \mid i \in \{1, \dots, n\} \} $ be a set of coins, where $ d_i \in \mathbb{Z}^+ $ is the denomination and $ a_i \in \mathbb{Z}^+ $ is the interestingness of coin $ i $. **Constraints** Find a subset $ S \subseteq \{1, \dots, n\} $ such that: - The set $ \{ d_i \mid i \in S \} $ can represent every integer $ k \in [1, b] $ as a subset sum. - The total interestingness $ \sum_{i \in S} a_i $ is minimized. **Objective** Minimize $ \sum_{i \in S} a_i $ subject to the constraint that $ \text{SubsetSum}( \{ d_i \mid i \in S \} ) \supseteq [1, b] $. If no such $ S $ exists, output $-1$. Otherwise, output $ |S| $ and the indices $ i \in S $ (in any order).

API Response (JSON)

{
  "problem": {
    "name": "H. Precise Shopping",
    "description": {
      "content": "When Baklazan goes shopping, he likes calculating how much he should pay and prepare that amount exactly. There are n coins in his wallet, numbered 1 through n. Coin i has denomination di. Also, each ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10113H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "When Baklazan goes shopping, he likes calculating how much he should pay and prepare that amount exactly. There are n coins in his wallet, numbered 1 through n. Coin i has denomination di. Also, each ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, b \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 42 $, $ 1 \\leq b \\leq 10^9 $.  \nLet $ C = \\{ (d_i, a_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be a set of coins, where $ d_i \\in \\mathbb{...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments