Dãy con của một dãy số là dãy mới được tạo thành sau khi bỏ đi một vài phần tử của dãy ban đầu (hoặc không bỏ phần tử nào. Ví dụ dãy là dãy con của day . Dãy rỗng (không gồm phần tử nào) là dãy con của mọi dãy số, dãy rỗng thì có tổng là .
Yêu cầu: Cho truy vấn, mỗi truy vấn gồm một cặp số . Với mỗi truy vấn, bạn hãy tìm dãy con của dãy có tổng lớn nhất, in ra tổng đó.
Dữ liệu vào:
Dòng đầu chứa hai số ;
Dòng tiếp theo gồm số nguyên ;
dòng tiếp theo, mỗi dòng là một cặp số nguyên dương .
Dữ liệu ra:
Ghi trên dòng, dòng thứ là đáp án truy vấn .
Ví dụ:
Dữ liệu vào:
5 2
-1 2 -3 4 -5
2 4
3 3
Dữ liệu ra:
6
0
Giới hạn:
Subtask số điểm có ;
Subtask số điểm còn lại không có ràng buộc bổ sung.
