#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

Gug is lazy to get out of his house, so he has tasked his AI to go grocery shopping for him. At the store, the AI has found a row of *N* mushrooms lined up in a row, numbered 0 to *N*-1 from left to right. The *i*th mushroom has deliciousness *D _{i}*, and weight

*W*grams. Some mushrooms can be rotten, and so can have negative deliciousness.

_{i}
Gug wishes to buy a consecutive segment of mushrooms (or no mushrooms at all). Unlike Gug, his AI is weak, and so can only carry a maximum of *X* grams of mushrooms before it collapses and dies. Help Gug choose a consecutive segment of mushrooms to buy such that the sum of their deliciousness is maximised.

## Input

The first line of input will contain two integers, *N* and *X*.

The second line of input will contain *N* integers, representing the array *D*.

The third line of input will contain *N* integers, representing the array *W*.

## Output

The output should contain one line with exactly one integer, the maximum sum of deliciousness of any valid segment of mushrooms the AI can buy.

## Limits

For all subtasks: 0 ≤ X ≤ sum of W_{i}, |D_{i}| ≤ 10^{6}, 1 ≤ W_{i} ≤ 10^{6}.

Subtask 1 (8%): 1 ≤ N ≤ 300.

Subtask 2 (24%): 1 ≤ N ≤ 2000.

Subtask 3 (17%): 1 ≤ N ≤ 200000, X = sum of W_{i}.

Subtask 4 (19%): 1 ≤ N ≤ 200000, D_{i} ≥ 0.

Subtask 5 (18%): 1 ≤ N ≤ 200000.

Subtask 6 (14%): 1 ≤ N ≤ 3000000.

Subtask 7 (0%): Sample Testcases.

## Sample Input 1

6 20 5 -1 2 -4 6 7 3 1 4 1 9 15

## Sample Output 1

8

## Sample Input 2

2 4 -1 -2 1 3

## Sample Output 2

0

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 8 | 22 | 2s | 256MB | Minimum |

2 | 24 | 42 | 2s | 256MB | Minimum |

3 | 17 | 21 | 2s | 256MB | Minimum |

4 | 19 | 20 | 2s | 256MB | Minimum |

5 | 18 | 102 | 2s | 256MB | Minimum |

6 | 14 | 112 | 2s | 256MB | Minimum |

7 | 0 | 2 | 2s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o supermarket -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512