Sphere Online Judge

SPOJ Problem Set (classical)

9861. Hotels Along the Croatian Coast

Problem code: HOTELS


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

Added by:Adrian Satja Kurdija
Date:2011-10-30
Time limit:1s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All
Resource:that would be me

hide comments
2014-07-18 14:57:08 Ankit Aggarwal
easy problem done in single try!!!
2014-07-17 08:08:30 ankur manchanda
my code took 2.45 sec still accepted .But the mentioned time limit is 1sec. Nevertheless my solution memory space is much better than the best solution submitted in C++ i.e 2.8M :)
Used scanf and printf instead of cin cout time 0.92 sec

Last edit: 2014-07-17 08:30:45
2014-06-28 23:55:53 Simarpreet Singh
changed long long to int and got ac from tle.. never thought constraints can have such a big impact ! :)

Last edit: 2014-06-28 23:56:09
2014-06-23 12:14:47 Aditya jain
very nice question learned a lot..

2014-06-12 14:09:05 Manu Narsaria
same code got AC in c++ but WA in c...
2014-06-11 14:51:38 Prakhar Gupta
yeahhh... my 100th on spoj :D
2014-06-10 10:58:14 Varun Bhardwaj
AC..0.96s
O(N)
nice prob
2014-06-04 01:00:17 JordanBelfort
easy :)
2014-06-02 21:28:38 Sagar Shah
yay!AC in first attempt.pretty easy.got just under 1 second phew!(0.88s)
just need fast i/o. int is enough to store 2^31.
2014-05-24 11:32:04 Shanks
easy straight forward.. use fast i/o and long long in o(n)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.