Trục thời gian là một mảng vô hạn được tạo ra bằng cách lặp đi lặp lại mảng gốc A (gồm N phần tử). Ví dụ A = [1, 2, 3] thì mảng vô hạn là [1, 2, 3, 1, 2, 3, 1, 2, 3...]. Bạn nhận được Q truy vấn, mỗi truy vấn yêu cầu tính tổng các phần tử nằm từ vị trí L đến vị trí R của mảng vô hạn này. (Vị trí đánh số từ 1).

Input:

Dòng 1: N, Q (1 <= N, Q <= 10^5).

Dòng 2: N số nguyên Ai (1 <= Ai <= 10^4).

Q dòng tiếp theo: Mỗi dòng 2 số nguyên L, R (1 <= L <= R <= 10^18).

Output: In ra Q dòng, mỗi dòng là tổng tính được.

Ví dụ:

Input:

3 2
1 2 3
1 4
2 5

Output:

7
8

(Giải thích: Đoạn từ 1 đến 4 là 1+2+3+1 = 7. Đoạn từ 2 đến 5 là 2+3+1+2 = 8).

Chuẩn bị quà bế giảng, cửa hàng có N loại kẹo. Loại thứ i có số lượng còn lại trong kho là Ai và giá bán lẻ là Bi đồng/chiếc. Cô giáo cần mua đúng M chiếc kẹo để tặng học sinh. Để tiết kiệm quỹ lớp, hãy lập trình tính số tiền tối thiểu cần bỏ ra. Dữ liệu đảm bảo tổng số lượng kẹo trong kho luôn lớn hơn hoặc bằng M.

Input:

Dòng 1: N, M (1 <= N <= 10^5, 1 <= M <= 10^9).

N dòng tiếp theo: Mỗi dòng 2 số nguyên Ai, Bi (1 <= Ai <= 10^9, 1 <= Bi <= 10^4).

Output: Số tiền tối thiểu cần dùng.

Ví dụ:

Input:

3 10
5 3
8 1
4 2

Output:

12

Mua 8 cái kẹo giá 1, 2 cái kẹo giá 2, tốn 12.

Sổ thu chi ghi lại chi phí của N ngày liên tiếp. Để kiểm tra tính hợp lý, nhân viên kế toán muốn đếm xem có bao nhiêu giai đoạn (là một chuỗi các ngày liên tiếp) mà tổng chi phí trong giai đoạn đó không vượt quá ngân sách cho phép là S. Các chi phí ghi nhận mỗi ngày đều là số nguyên dương.

Input:

Dòng 1: N, S (1 <= N <= 10^5, 1 <= S <= 10^14).

Dòng 2: N số nguyên dương Ai (1 <= Ai <= 10^9).

Output: Số lượng giai đoạn thỏa mãn.

Ví dụ:

Input:

4 5
1 2 3 4

Output:

5

(Giải thích: Các giai đoạn là: [1], [2], [3], [4], [1, 2]).

Thuật toán nén làm mất toàn bộ dấu cách của một đoạn văn bản chỉ còn lại xâu S. Bạn có một cuốn từ điển chứa K từ chuẩn. Hãy xác định xem có thể chia xâu S thành một chuỗi các từ ngăn cách nhau bởi dấu cách sao cho mọi từ đều xuất hiện trong từ điển hay không. Một từ trong từ điển có thể được sử dụng nhiều lần.

Input:

Dòng 1: Xâu S (Độ dài <= 1000).

Dòng 2: Số nguyên K (1 <= K <= 1000).

K dòng tiếp theo: Mỗi dòng chứa 1 từ hợp lệ trong từ điển (độ dài <= 50).

Output: In ra YES nếu có thể tách từ, ngược lại in NO.

Ví dụ:

Input:

hoccongnghe
3
hoc
cong
nghe

Output:

YES