D. Data Center

Codeforces

IDCF10051D

Time2000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

The startup "Booble" has shown explosive growth and now it needs a new data center with the capacity of m petabytes. Booble can buy servers, there are n servers available for purchase: they have equal price but different capacities. The i-th server can store ai petabytes of data. Also they have different energy consumption — some servers are _low voltage_ and other servers are not. Booble wants to buy the minimum number of servers with the total capacity of at least m petabytes. If there are many ways to do it Booble wants to choose a way to maximize the number of _low voltage_ servers. Booble doesn't care about exact total capacity, the only requirement is to make it at least m petabytes. The first line contains two integer numbers n and m (1 ≤ n ≤ 2·105, 1 ≤ m ≤ 2·1015) — the number of servers and the required total capacity. The following n lines describe the servers, one server per line. The i-th line contains two integers ai, li (1 ≤ ai ≤ 1010, 0 ≤ li ≤ 1), where ai is the capacity, li = 1 if server is _low voltage_ and li = 0 in the opposite case. It is guaranteed that the sum of all ai is at least m. Print two integers r and w on the first line — the minimum number of servers needed to satisfy the capacity requirement and maximum number of _low voltage_ servers that can be bought in an optimal r servers set. Print on the second line r distinct integers between 1 and n — the indices of servers to buy. You may print the indices in any order. If there are many solutions, print any of them. In the first example any pair of servers which includes the server 2 is a correct output. ## Input The first line contains two integer numbers n and m (1 ≤ n ≤ 2·105, 1 ≤ m ≤ 2·1015) — the number of servers and the required total capacity. The following n lines describe the servers, one server per line. The i-th line contains two integers ai, li (1 ≤ ai ≤ 1010, 0 ≤ li ≤ 1), where ai is the capacity, li = 1 if server is _low voltage_ and li = 0 in the opposite case.It is guaranteed that the sum of all ai is at least m. ## Output Print two integers r and w on the first line — the minimum number of servers needed to satisfy the capacity requirement and maximum number of _low voltage_ servers that can be bought in an optimal r servers set.Print on the second line r distinct integers between 1 and n — the indices of servers to buy. You may print the indices in any order. If there are many solutions, print any of them. [samples] ## Note In the first example any pair of servers which includes the server 2 is a correct output.

**Definitions** Let $ s \in \{ \text{digits}, \texttt{,}, \texttt{Z}, \texttt{O} \}^* $ be the encrypted string, with $ 1 \leq |s| \leq 10^5 $. **Constraints** Each character in $ s $ is one of: - Digits: $ \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} $, - Symbols: $ \texttt{,} $, $ \texttt{Z} $, $ \texttt{O} $. **Objective** Recover the original string by applying the inverse of the encryption algorithm, where: - $ \texttt{Z} \mapsto 0 $, - $ \texttt{O} \mapsto 1 $, - $ \texttt{,} \mapsto \text{space} $, - Digits remain unchanged. Output the resulting string.

API Response (JSON)

{
  "problem": {
    "name": "D. Data Center",
    "description": {
      "content": "The startup \"Booble\" has shown explosive growth and now it needs a new data center with the capacity of m petabytes. Booble can buy servers, there are n servers available for purchase: they have equal",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10051D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The startup \"Booble\" has shown explosive growth and now it needs a new data center with the capacity of m petabytes. Booble can buy servers, there are n servers available for purchase: they have equal...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{ \\text{digits}, \\texttt{,}, \\texttt{Z}, \\texttt{O} \\}^* $ be the encrypted string, with $ 1 \\leq |s| \\leq 10^5 $.\n\n**Constraints**  \nEach character in $ s $ is one of: ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments