Algorithm

problem link- https://www.spoj.com/problems/HOTELS/

HOTELS - Hotels Along the Croatian Coast

#sliding-window-1

 

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 & Try With Live Editor

Input

x
–
+
cmd
5 12
2 1 3 4 5

Output

x
–
+
cmd
12
Advertisements

Demonstration

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

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python