Trong nhà Nam hiện đang có n ổ cắm điện rời. Số lượng chỗ cắm trên mỗi ổ cắm điện này lần lượt là ~a_1, a_2, a_3,…, a_n~ chỗ cắm. Trên tường nhà Nam có một chỗ cắm cố định đang có điện. Vậy để cho một ổ cắm điện rời có điện thì phải cắm ổ cắm đó vào chỗ cắm cố định trên tường. Chúng ta cũng có thể cắm ổ cắm điện rời này vào một ổ cắm điện rời khác đang có điện.

Nam có ~m~ thiết bị sử dụng điện, để sử dụng thì các thiết bị này cần được cắm vào ổ cắm trên tường hoặc ổ cắm rời đang có điện. Bạn hãy giúp Nam tìm ra số ổ cắm rời ít nhất cần dùng để có thể sử dụng tất cả ~m~ thiết bị điện này.

*Dữ liệu: *

CAMDIEN.INP gồm:

• Dòng thứ nhất gồm 2 số nguyên ~n, m~. Dữ liệu vào đảm bảo ~1 ≤ n, m ≤ 10^5~ , ~n~ là số lượng ổ cắm và ~m~ là số lượng thiết bị.

• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, …, a_n~ là số chỗ cắm trên các ổ cắm rời tương ứng, mỗi số cách nhau một khoảng trắng, dữ liệu vào đảm bảo ~1 ≤ a_i ≤ 10^5~ .

*Kết quả: *

CAMDIEN.OUT là số nguyên cho biết số ổ cắm rời ít nhất cần sử dụng là bao nhiêu. Nếu đã sử dụng hết tất cả ổ cắm rời mà vẫn không đủ, in ra -1.

Ví dụ 1:

CAMDIEN.INP

3 4 
3 2 2

CAMDIEN.OUT

2

Ví dụ 2:

CAMDIEN.INP

5 5 
1 3 1 2 1

CAMDIEN.OUT

-1

Cho một xâu ký tự S chỉ gồm các chữ cái thưởng a…z. Xâu đối xứng là xâu kí tự mà khi viết từ phải qua trái hay từ trái qua phải thì xâu đó không thay đổi. Ví dụ: madam, coi là các xâu đối xứng.

• Cho xâu aammmda thì cần bỏ 2 ký tự a và m thì xâu còn lại là ammda và xếp lại thành madam là xấu đối xứng.

• Cho xâu aaabbcc thì không cần bỏ ký tự thì xâu đó xếp lại thành bcaaacb là xâu đối xứng.

Yêu cầu: Với xâu ký tự S cho trước, hãy tính số ký tự bỏ đi ít nhất để các ký tự còn lại có thể sắp xếp được thành một xâu đối xứng.

Dữ liệu vào: Đọc từ file văn bản XAUDX.INP chứa một xâu ký tự 5 có n ký tự ~(n = 10^5)~ chỉ gồm các ký tự chữ cái thường a...

Kết quả: Ghi ra file văn bản XAUDX.OUT một số nguyên là số lượng kỳ ít nhất cần bỏ để các ký tự còn lại có thể sắp xếp được thành một xâu đối xứng.

Ví dụ:

XAUDX.INP

aammmda

XAUDX.OUT

2

XAUDX.INP

aaabbcc

XAUDX.OUT

0

Cho dãy N số nguyên ~a_1, a_2, ..., a_n~. Người ta gọi một đoạn gồm các phần tử liên tiếp bất kỳ trong dãy ban đầu là đoạn con. Hai đoạn con là khác nhau nếu tồn tại ít nhất một phần tử không thuộc cả hai đoạn. Ví dụ dãy: ~{a_1,a_2,a_3, a_4}~ thì có mười đoạn con là: ~{a_1}, {a_2}, {a_3}, {a_4}, {a_1, a_2}, {a_1, a_3}, {a_1, a_4}, {a_2, a_3}, {a_2, a_4}, {a_3, a_4}, {a_1, a_2, a_3}, {α_1, a_2, a_4}, {a_1, a_3, a_4}, {a_2, a_3, a_4}, {a_1, a_2, a_3, a_4}~.

Hãy đếm số đoạn con mà tổng các lũy thừa bậc M của các phần tử trong đoạn đó chia hết cho K.

Dữ liệu: vào từ file DOANCON.INP gồm hai dòng:

Dòng đầu chứa ba số nguyên dương ~N,M,K (1 <N<10^5;1<M<10^18, 1≤ K≤ 10^5)~;</p>

Dòng thứ hai chứa N số tự nhiên ~a_1, a_2, ..., a_n (1≤ a_i ≤ 10^50)~.

Kết quả: ghi ra file DOANCON.OUT số đoạn con mà có tổng các lũy thừa bậc M của các phần tử chia hết cho K.

Ví dụ 1 :

DOANCON.INP

4 1 3
3 2 1 5

DOANCON.OUT

4

Ví dụ 2 :

DOANCON.INP

4 2 3
3 2 1 5

DOANCON.OUT 3

Giải thích

vd1: Bốn đoạn con gồm: {3}, {2, 1}, {3, 2, 1} và (1,5)

vd2: Ba đoạn con gồm: {3}; {2, 1, 5}; (3, 2, 1,5}