## HOTELS - Hotels Along the Croatian Coast

There are N hotels along the beautiful Adriatic coast. Each hotel has its value in Euros.

Sroljo has won M Euros on the lottery. Now he wants to buy a sequence of consecutive hotels, such that the sum of the values of these consecutive hotels is as great as possible - but not greater than M.

You are to calculate this greatest possible total value.

### Input

In the first line of the input there are integers N and M (1 ≤ N ≤ 300 000, 1 ≤ M < 231).

In the next line there are N natural numbers less than 106, representing the hotel values in the order they lie along the coast.

### Output

Print the required number (it will be greater than 0 in all of the test data).

### Example

 input ```5 12 2 1 3 4 5``` output `12` input ```4 9 7 3 5 6``` output `8`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>

using namespace std;

int main(){
long long n,m;
scanf("%lld%lld",&n,&m);
long long a[n];
for(long long i=0;i<n;i++){
scanf("%lld",&a[i]);
}
long long maxi=0;
long long temp=a[0];
long long start=0;
long long i;
for(i=1;i<=n;i++){
while(temp>m&&start<i-1){
temp-=a[start];
start++;
}
maxi=max(maxi,temp);
temp+=a[i];
}
printf("%lld\n",maxi);
return 0;
}``````
Copy The Code &

Input

cmd
5 12
2 1 3 4 5

Output

cmd
12
Advertisements

## Demonstration

SPOJ Solution-Hotels Along the Croatian Coast-Solution in C, C++, Java, Python