Trong giờ sinh hoạt của lớp 9A, cô giáo chủ nhiệm chia học sinh lớp 9A thành hai tổ để tổ chức các trò chơi tập thể và bạn An được chia vào tổ \(1\). Cô chủ nhiệm cho trước hai chuỗi A, B chứa các chữ cái trong bảng chữ cái tiếng Anh (có cả chữ hoa và chữ thường). Chuỗi A có độ dài \(n\), chuỗi B có độ dài \(m\). Nếu tổ nào đếm số lần xuất hiện các hoán vị của chuỗi A trong chuỗi B chính xác sẽ chiến thắng.

Bạn hãy giúp An tìm đáp án để chiến thắng trò chơi trên.

Input

• Dòng duy nhất chứa hai số nguyên \(n\) (\(n \leq 1000\)) và \(m\) (\(m \leq 10^6\)), \(n\) kí tự chuỗi A và \(m\) kí tự chuỗi B

Output

• Gồm một dòng duy nhất là số lần xuất hiện các hoán vị của chuỗi A trong chuỗi B.

Example

4 11
cAda
AbrAcadAbRa

2

Trò chơi của lớp 9A là trò chơi ghép tranh. Cô chủ nhiệm cho một bức tranh có \(N\) mảnh ghép và một số nguyên \(K\) (\(1 \leq K \leq N \leq 50\)). Lần lượt, từng tổ sẽ thay phiên nhau lên ghép tranh với số mảnh ghép mỗi lần không được vượt quá \(K\).

An nhận thấy rằng cần phải tìm tất cả các cách ghép tranh khác nhau để chiến thắng trò chơi. Một cách ghép tranh khác nhau nếu tồn tại ít nhất một mảnh ghép được ghép trong một cách nhưng bị bỏ qua ở cách khác.

Xác định số cách ghép tranh khác nhau để An có thể hoàn thành bức tranh.

Input

• Gồm một dòng lần lượt là hai số nguyên \(N\) và \(K\).

Output

• Gồm một dòng duy nhất là số cách ghép tranh khác nhau để An có thể hoàn thành bức tranh.

Example

4 3

7

Trò chơi thứ ba của lớp 9A là trò chơi xếp các khối hình vuông. Cô chủ nhiệm cho mỗi tổ N (\(0 < N ≤ 10^5\)) khối hình vuông, các khối hình vuông của tổ 1 giống các khối hình vuông của tổ 2. Trên mỗi khối hình vuông có một số nguyên \(a_i\) (\(1 \leq i ≤ N, 1 ≤ a_i ≤ 1000\)) thể hiện khả năng cách nhiệt của khối hình vuông đó. Nếu xếp lần lượt các khối hình vuông theo trình tự \(a_1, a_2,... a_n\), thì độ cách nhiệt của khối là:

\(a_1 + a_2 + ... + a_n + max(0, a_2 - a_1) + max(0, a_3 - a_2) + ... + max(0, a_N - a_{N - 1})\)

Bạn hãy giúp An xếp các khối hình vuông sao cho độ cách nhiệt của cả khối là lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (số lượng khối hình vuông).
• \(n\) dòng tiếp theo, mỗi dòng là các giá trị \(a_i\) (Khả năng cách nhiệt của từng khối hình vuông).

Output

• Gồm một dòng duy nhất là độ cách nhiệt lớn nhất có thể đạt được.

Example

4
5
4
1
7

24

Để kết thúc buổi sinh hoạt lớp 9A vui vẻ, cô chủ nhiệm đã chuẩn bị N (\(N \leq 500000\), \(N\) là một số chẵn) phần quà cho hai tổ. Mỗi tổ sẽ dán một giá trị ưa thích (là một số nguyên dương nhỏ hơn hoặc bằng 100) mà mình nghĩ vào phần quà. Sau đó, cô chủ nhiệm chia cho mỗi tổ \(\frac{N}{2}\) phần quà sao cho tổng giá trị ưa thích của hai tổ là lớn nhất.

Bạn hãy giúp cô chủ nhiệm tìm tổng giá trị ưa thích lớn nhất của hai tổ theo cách chia quà trên.

Input

• Dòng đầu tiên chứa số nguyên \(N\) (số lượng phần quà).
• \(N\) dòng tiếp theo, mỗi dòng gồm 2 số \(a_i, b_i\) ($ 1 \leq a_i, b_i \leq 100$) là giá trị ưa thích của 2 tổ.

Output

• Gồm một dòng duy nhất là tổng giá trị ưa thích lớn nhất của hai tổ theo cách chia quà trên.

Example

4
1 2
2 3
3 5
2 1

11