Tổng đoạn con lớn thứ k

Cho dãy số nguyên $a_1,a_2,\dots ,a_n$ gồm $n$ phần tử. Xét tập hợp gồm tất cả các tổng đoạn con liên tiếp (không rỗng) có dạng $a_l+a_{l+1}+\dots +a_r$ với $1\le l\le r\le n$. Hai đoạn được xem là khác nhau nếu cặp chỉ số $(l,r)$ khác nhau, kể cả khi tổng của chúng bằng nhau. Tổng số lượng đoạn như vậy là $\frac{n(n+1)}{2}$.

Hãy sắp xếp tất cả các tổng đoạn con đó theo thứ tự giảm dần và in ra giá trị thứ $k$ trong dãy đã sắp xếp. Phần tử của dãy $a$ có thể âm.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một số nguyên — tổng đoạn con lớn thứ $k$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le k\le {\displaystyle \frac{n(n+1)}{2}}$
• $|a_i|\le {10}^9$

Ví dụ