Bài tập

Cho một mảng gồm \(n\) số nguyên và số nguyên \(t\).

Yêu cầu: Tìm mảng con gồm những phần tử liên tiếp dài nhất sao cho tổng tất cả các phần tử của mảng này không quá \(t\). Và số lượng phần tử của mảng này chính là kết quả cần tìm.

Input

• Dòng thứ nhất chứa hai số nguyên \(n,t(1\le n\le 10^5;1\le t\le 10^9)\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n(1\le a_i\le 10^4)\)

Output

• In ra giá trị cần tìm.

Example

4 4
1 2 1 2

3

Trong một vương quốc nọ, có một mỏ khoáng sản quý hiếm trải dài theo một con suối. Mỏ được chia thành \(L\) khu vực, được đánh số từ \(1\) đến \(L\). Mỗi khu vực thứ \(i\) chứa một lượng khoáng sản có giá trị là \(C_i\). Vua của vương quốc muốn thuê \(G\) đội thợ mỏ để khai thác toàn bộ mỏ khoáng sản này.

Để việc khai thác được hiệu quả và công bằng, nhà vua quyết định chia con suối thành \(G\) đoạn liên tiếp, và mỗi đội thợ mỏ sẽ chịu trách nhiệm khai thác một đoạn. Chi phí cho việc khai thác một khu vực được tính bằng cách lấy giá trị khoáng sản của khu vực đó nhân với tổng số khu vực trong đoạn mà nó thuộc về. Tổng chi phí khai thác của cả mỏ sẽ là tổng chi phí của tất cả các khu vực.

Nhà vua muốn tìm cách phân chia mỏ khoáng sản thành \(G\) đoạn sao cho tổng chi phí khai thác là nhỏ nhất. Bạn, một vị quan cận thần tài ba, được giao nhiệm vụ tìm ra cách phân chia tối ưu này.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên \(L\) và \(G\) (\(1 \le L \le 8000\), $1 \le G \le min(800, L) $).
• \(L\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(C_i\) (\(1 \le C_i \le 10^9\)), là giá trị của dãy số.

Output

In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất tìm được.

Example

6 3
11 11 11 24 26 100

299

Scoring

• Subtask \(1\) (\(30\%\) số điểm) : \(1 \leq L \leq 20\).
• Subtask \(2\) (\(30\%\) số điểm) : \(1 \leq L \leq 800\).
• Subtask \(3\) (\(40\%\) số điểm) : \(1 \leq L \leq 8000\).

Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1,A_2,…,A_n\). Mỗi phần tử có giá trị không vượt quá \(10^9\) và \(n≤ 10^5\). Một cặp số được gọi là cặp tương đồng với \(x\), nếu cặp số này có tổng bằng số \(x\) cho trước nào đó.

Yêu cầu: Hãy đếm xem trong dãy số \(A\) có bao nhiêu cặp số (\(A_i;A_j\)) tương đồng với \(x\) (có nghĩa là \(A_i+ A_j=x\)) với \(i<j\).

Input

• Dòng đầu tiên chứa dãy số \(n,x\) (\(n≤10^5,x≤10^6\)).
• Dòng thứ 2 chứa \(n\) phần tử của dãy số \(A\) (\(A_i≤10^9\)).

Output

• Ghi ra một số nguyên là cặp đôi tương đồng của dãy số.

Example

7 6
1 2 4 3 4 5 3

4

Để nắm bắt được tình hình đọc sách tại thư viện A quản lí thư viện đã yêu cầu cô nhân viên thư viện thống kê số lượt người tham gia đọc sách tại thư viện và đếm số ngày nhiều nhất có cùng lượt người đọc.

Cô nhân viên thư viện ghi lại liệt kê \(n\) ngày đọc sách với số lượt người đọc của từng ngày cụ thể, em hãy giúp cô nhân viên thư viện phân việc còn lại là đưa ra tổng số lượt người đọc sách và số ngày có cùng lượt người đọc là nhiều nhất có thể.

Input

Dữ liệu vào: Đọc từ tệp TK.INP có cấu trúc:

• Dòng đầu ghi số nguyên dương \(n\) (\(n \le 10^5\)).
• Dòng thứ hai ghi \(n\) số nguyên không âm \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^5, i = 1, 2, 3, ..., n\)).

Output

Dữ liệu ra: Ghi vào tệp TK.OUT có cấu trúc:

• Dòng đầu ghi tổng số lượt người tham gia đọc sách.
• Dòng thứ hai ghi số ngày nhiều nhất có cùng lượt người đọc. Trường hợp tất cả các ngày không có cùng lượt người đọc thì ghi -1.

Example

6
15 60 50 25 20 50

220
2

6
15 60 50 25 20 55

225
-1

Scoring

• Có \(60\%\) số test ứng với \(60\%\) số điểm của bài có \(N \leq 10^3\).
• Có \(40\%\) số test khác ứng với \(40\%\) số điểm với trường hợp còn lại.