E. Wardrobe

Codeforces

IDCF956E

Time1000ms

Memory256MB

Difficulty—

dpgreedy

Olya wants to buy a custom wardrobe. It should have _n_ boxes with heights _a_1, _a_2, ..., _a__n_, stacked one on another in some order. In other words, we can represent each box as a vertical segment of length _a__i_, and all these segments should form a single segment from 0 to without any overlaps. Some of the boxes are important (in this case _b__i_ = 1), others are not (then _b__i_ = 0). Olya defines the _convenience_ of the wardrobe as the number of important boxes such that their bottom edge is located between the heights _l_ and _r_, inclusive. You are given information about heights of the boxes and their importance. Compute the maximum possible convenience of the wardrobe if you can reorder the boxes arbitrarily. ## Input The first line contains three integers _n_, _l_ and _r_ (1 ≤ _n_ ≤ 10 000, 0 ≤ _l_ ≤ _r_ ≤ 10 000) — the number of boxes, the lowest and the highest heights for a bottom edge of an important box to be counted in convenience. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 10 000) — the heights of the boxes. It is guaranteed that the sum of height of all boxes (i. e. the height of the wardrobe) does not exceed 10 000: Olya is not very tall and will not be able to reach any higher. The second line contains _n_ integers _b_1, _b_2, ..., _b__n_ (0 ≤ _b__i_ ≤ 1), where _b__i_ equals 1 if the _i_\-th box is important, and 0 otherwise. ## Output Print a single integer — the maximum possible convenience of the wardrobe. [samples] ## Note In the first example you can, for example, first put an unimportant box of height 2, then put an important boxes of sizes 1, 3 and 2, in this order, and then the remaining unimportant boxes. The convenience is equal to 2, because the bottom edges of important boxes of sizes 3 and 2 fall into the range \[3, 6\]. In the second example you have to put the short box under the tall box.

Samples

Input #1

5 3 6
3 2 5 1 2
1 1 0 1 0

Output #1

Input #2

2 2 5
3 6
1 1

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. Wardrobe",
    "description": {
      "content": "Olya wants to buy a custom wardrobe. It should have _n_ boxes with heights _a_1, _a_2, ..., _a__n_, stacked one on another in some order. In other words, we can represent each box as a vertical segmen",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF956E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Olya wants to buy a custom wardrobe. It should have _n_ boxes with heights _a_1, _a_2, ..., _a__n_, stacked one on another in some order. In other words, we can represent each box as a vertical segmen...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments