Lightweight Knapsack

AtCoder

IDabc442_g

Time4000ms

Memory256MB

Difficulty—

There are $N$ types of items. The $i$\-th type of item has **weight** $W_i$ and **value** $V_i$, and you have $K_i$ of them. When choosing some (possibly zero) items from these $K_1+\dots+K_N$ items so that the total weight does not exceed $C$, find the maximum possible total value of the chosen items. ## Constraints * $1\leq N \leq 2\times 10^5$ * $1\leq C \leq 2\times 10^9$ * $1\leq W_i \leq 3$ * $1\leq V_i \leq 10^9$ * $1\leq K_i \leq 10^9$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $C$ $W_1$ $V_1$ $K_1$ $W_2$ $V_2$ $K_2$ $\vdots$ $W_N$ $V_N$ $K_N$ [samples]

Samples

Input #1

Output #1

16

If you choose $1$ item of the $1$\-st type, $2$ items of the $2$\-nd type, and $1$ item of the $3$\-rd type, the total weight is $3\times 1+1\times 2+2\times 1=7\ (\leq C)$ and the total value is $5\times 1+2\times 2+7\times 1=16$, which is the maximum.

Input #2

2 1
3 442 442
2 442 442

Output #2

0

You cannot choose any items.

Input #3

15 913575467
1 60505998 818008580
2 121011861 138996221
3 181517958 501899080
1 60506027 840594328
3 181517875 350034067
1 60505924 155374934
3 181517816 910748511
1 60506042 545531545
3 181517877 797829355
3 181517837 164163676
1 60505894 353195922
1 60505912 954291757
1 60506022 160449218
3 181517873 404011431
1 60506043 782177068

Output #3

55276836358648682

API Response (JSON)

{
  "problem": {
    "name": "Lightweight Knapsack",
    "description": {
      "content": "There are $N$ types of items. The $i$\\-th type of item has **weight** $W_i$ and **value** $V_i$, and you have $K_i$ of them. When choosing some (possibly zero) items from these $K_1+\\dots+K_N$ items s",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc442_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ types of items. The $i$\\-th type of item has **weight** $W_i$ and **value** $V_i$, and you have $K_i$ of them.\nWhen choosing some (possibly zero) items from these $K_1+\\dots+K_N$ items s...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments