ABA12E - Shooting the balloons!

no tags 

Dhinakaran is very fond of games. Shooting the balloons is his favourite. In this game, there are ‘n’ balloons which are arranged in a line. Every balloon has a unique number which is the number of points earned if that balloon is shot. A constraint here is that you should shoot contiguous balloons. So, Dhinakaran wanted to find the maximum number of points he could earn. He sought help from a friend who told him that it was the famous maximum contiguous sum problem. So Dhinakaran learnt about it and was happy. But Dhinakaran is not someone who gets satisfied so easily. He wanted to find the k-th smallest possible contiguous sum! Now, his friend was not able to solve this. So he came to me. I suggested that he approach you. You are a great coder, aren’t you? Help him out.

There will be at least 1 balloon and at most 50000 balloons, and each balloon can have at least 0 point and at most 109 points.

Input

The first line of each data set contains the number of balloons and value of k.

1 <= k <= (n * (n + 1)) / 2

The second line contains N space separated integers.

Output

The output for each test case should be a single line containing the k-th smallest possible contiguous sum of points that could be achieved.

Example

Input:
5 3
1 2 3 4 5

Output:
3

Explanation of Sample Case

The first 5 smallest contiguous subsequences are 1, 2, 3, 1 + 2, 4


hide comments
onlyerror: 2022-06-29 16:20:22

Best problem on binary search

kkmeliodus: 2019-09-06 15:34:09

how is this problem done

code_ster: 2019-02-14 10:33:09

How many data sets does this provide?

(Tjandra Satria Gunawan)(曾毅昆): 2015-01-14 14:37:45

warning: input is badly formated

(Tjandra Satria Gunawan)(曾毅昆): 2015-01-14 13:34:35

Yes ballon can have 0 points, It cost me 2 WA.
Thank you abhiranjan for your report.
Problem description has been updated.

abhiranjan: 2012-05-27 07:30:04

Correction:

...and each balloon can have atleast 1 0 point and atmost 1e9 points.

Teddy Budiono Hermawan: 2012-05-23 08:23:05

N is the number of balloons.

There will be atleast 1 balloon and atmost 50000 balloons

Rahul Bobhate: 2012-03-26 21:53:59

What is the range of n ?


Added by:Kashyap Krishnakumar
Date:2012-01-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem