E. Selling Souvenirs

Codeforces

IDCF808E

Time2000ms

Memory256MB

Difficulty—

binary searchdpgreedyternary search

English · Original

Chinese · Translation

Formal · Original

After several latest reforms many tourists are planning to visit Berland, and Berland people understood that it's an opportunity to earn money and changed their jobs to attract tourists. Petya, for example, left the IT corporation he had been working for and started to sell souvenirs at the market. This morning, as usual, Petya will come to the market. Petya has _n_ different souvenirs to sell; _i_th souvenir is characterised by its weight _w__i_ and cost _c__i_. Petya knows that he might not be able to carry all the souvenirs to the market. So Petya wants to choose a subset of souvenirs such that its total weight is not greater than _m_, and total cost is maximum possible. Help Petya to determine maximum possible total cost. ## Input The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 100000, 1 ≤ _m_ ≤ 300000) — the number of Petya's souvenirs and total weight that he can carry to the market. Then _n_ lines follow. _i_th line contains two integers _w__i_ and _c__i_ (1 ≤ _w__i_ ≤ 3, 1 ≤ _c__i_ ≤ 109) — the weight and the cost of _i_th souvenir. ## Output Print one number — maximum possible total cost of souvenirs that Petya can carry to the market. [samples]

经过几次最近的改革，许多游客计划访问贝兰，贝兰人意识到这是赚钱的机会，纷纷转行以吸引游客。例如，Petya 离开了他之前工作的 IT 公司，开始在集市上售卖纪念品。今天早上，和往常一样，Petya 将来到集市。Petya 有 #cf_span[n] 件不同的纪念品要卖；第 #cf_span[i] 件纪念品的重量为 #cf_span[wi]，价值为 #cf_span[ci]。Petya 知道他可能无法携带所有纪念品去集市。因此，Petya 希望选择一个纪念品子集，使得其总重量不超过 #cf_span[m]，且总价值尽可能大。帮助 Petya 确定可能的最大总价值。第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n ≤ 100000], #cf_span[1 ≤ m ≤ 300000]) —— Petya 的纪念品数量和他能携带到集市的总重量限制。接下来 #cf_span[n] 行，每行包含两个整数 #cf_span[wi] 和 #cf_span[ci] (#cf_span[1 ≤ wi ≤ 3], #cf_span[1 ≤ ci ≤ 109]) —— 第 #cf_span[i] 件纪念品的重量和价值。请输出一个数字 —— Petya 能携带到集市的纪念品可能的最大总价值。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n ≤ 100000], #cf_span[1 ≤ m ≤ 300000]) —— Petya 的纪念品数量和他能携带到集市的总重量限制。接下来 #cf_span[n] 行，每行包含两个整数 #cf_span[wi] 和 #cf_span[ci] (#cf_span[1 ≤ wi ≤ 3], #cf_span[1 ≤ ci ≤ 109]) —— 第 #cf_span[i] 件纪念品的重量和价值。 ## Output 请输出一个数字 —— Petya 能携带到集市的纪念品可能的最大总价值。 [samples]

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ denote the number of souvenirs and maximum allowable weight, respectively. Let $ W = (w_1, w_2, \dots, w_n) $ and $ C = (c_1, c_2, \dots, c_n) $ be sequences of weights and costs, where $ w_i \in \{1,2,3\} $ and $ c_i \in \mathbb{Z}^+ $ for all $ i \in \{1, \dots, n\} $. **Constraints** 1. $ 1 \leq n \leq 100000 $ 2. $ 1 \leq m \leq 300000 $ 3. $ 1 \leq w_i \leq 3 $ for all $ i \in \{1, \dots, n\} $ 4. $ 1 \leq c_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Find a subset $ S \subseteq \{1, \dots, n\} $ such that: $$ \sum_{i \in S} w_i \leq m $$ and the total cost $$ \sum_{i \in S} c_i $$ is maximized.

Samples

Input #1

1 1
2 1

Output #1

Input #2

2 2
1 3
2 2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "E. Selling Souvenirs",
    "description": {
      "content": "After several latest reforms many tourists are planning to visit Berland, and Berland people understood that it's an opportunity to earn money and changed their jobs to attract tourists. Petya, for ex",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF808E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "After several latest reforms many tourists are planning to visit Berland, and Berland people understood that it's an opportunity to earn money and changed their jobs to attract tourists. Petya, for ex...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "经过几次最近的改革，许多游客计划访问贝兰，贝兰人意识到这是赚钱的机会，纷纷转行以吸引游客。例如，Petya 离开了他之前工作的 IT 公司，开始在集市上售卖纪念品。\n\n今天早上，和往常一样，Petya 将来到集市。Petya 有 #cf_span[n] 件不同的纪念品要卖；第 #cf_span[i] 件纪念品的重量为 #cf_span[wi]，价值为 #cf_span[ci]。Petya 知道他可...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of souvenirs and maximum allowable weight, respectively.  \nLet $ W = (w_1, w_2, \\dots, w_n) $ and $ C = (c_1, c_2, \\dots, c_n) $ be se...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments