Noel sắp tới và Chưng đang lên kế hoạch làm những chiếc bánh su kem tặng cho Quýt. Mỗi chiếc bánh sẽ có một hương vị nhất định và các su kem có cùng vị sẽ được bỏ chung 1 hộp. Sau khi đóng gói các su kem vào hộp, Chưng nhận ra để những điều tốt đẹp và may mắn nhất đến với Quýt thì số bánh trong hộp phải là 1 số may mắn, trong đó số may mắn là số chỉ có chữ số 4 hoặc 7. Vì vậy cậu ấy sẽ đem những chiếc bánh từ hộp này bỏ vào hộp kia để cho số bánh trong hộp tạo thành số may mắn. Tuy nhiên việc này sẽ khiến Chưng mất một năng lượng sức khỏe.

Dưới tình hình khói bụi của Sài Gòn, Chưng đang bị ho sốt và cảm nặng bạn hãy cảnh báo cho Chưng biết năng lượng tối thiểu để có thể tạo nên một hộp su kem may mắn. Biết rằng một hộp bánh su kem sẽ may mắn nếu số bánh trong hộp là một số may mắn.

Lưu ý: "Bỏ từ hộp này vào hộp kia" là bỏ tất cả bánh từ hộp này sang hộp kia.

Input

• Dòng đầu tiên gồm hai số nguyên ~N, M~ với ~1 \le N, M \le 10^5~. Ngĩa là số bánh su kem mà Chưng đã làm và các su kem sẽ được đánh số từ ~1~ đến ~n.~

• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u, v~ với ~1 \le u, v \le N~ và ~u \neq v~, mô tả hai chiếc bánh su kem ~u~ và ~v~ được bỏ chung một hộp. Những chiếc bánh su kem không được nhắc đến sẽ được hiểu là nằm riêng một hộp.

Output

Một dòng duy nhất là năng lượng tối thiểu để tạo nên su kem may mắn, nếu không có cách nào hãy in ra ~-1~.

Sample Input 1

4 2 
1 2
2 1

Sample Output 1

2

Giải thích:

Ta sẽ bỏ su kem số ~3~ và su kem số ~4~ vào hộp chưa su kem ~1,2~. Việc này sẽ khiến Chưng mất ~2~ năng lượng.

Su kem ăn thì rất ngon, nhưng ăn nhiều quá thì lại không tốt...

Sau bao ngày tìm tồi nghiên cứu Chưng đã tìm ra cho một mình cách ăn so healthy đối với những chiếc bánh su kem. Cụ thể cách ăn đó như sau: Giả sử Chưng có cho mình N chiếc bánh su kem trên bàn được đánh số từ 1 đến N và mỗi chiếc sẽ có một độ béo là x với ~1 \le x_i \le 10^6~. Để không bị béo Chưng sẽ chia những chiếc bánh này thành G đoạn liên tiếp và sẽ ăn trong G ngày. Biết rằng nếu ăn những chiếc bánh từ vị trí i đến vị trí j Chưng sẽ mập lên một lượng ~min \sum_{s = i}^{j} |x_s - v|^k~ với ~v~ là số nguyên nào đó.

Tuy tìm được cách ăn healthy trên nhưng cậu ấy lại không thể nào cưỡng lại được độ ngon của những chiếc bánh và tương lai sẽ dẫn đến việc bị bỏ rơi do mập, nên bạn hãy giúp cậu ấy tìm khối lượng tăng lên ít nhất nếu cậu ấy ăn healthy như trên trong G ngày.

Input

• Dòng đầu tiên gồm ba số nguyên ~N, G, K~ với ~1 \le N, G \le 2.10^3~ , ~1 \le K \le 2~.

• ~N~ số tiếp theo là độ béo của từng chiếc bánh với ~1 \le x_i \le 10^6~. Trong đó ~x_i \lt x_{i+1}~, ~0 \le i\lt N~

Output

Một dòng duy nhất là khối lượng tối thiểu mà Chưng sẽ tăng lên khi ăn trong ~G~ ngày.

Sample Input 1

5 2 1
1 2 3 4 5

Sample Output 1

3

Giải thích:

Ngày đầu tiên Chưng sẽ ăn các chiếc bánh từ vị trí ~1~ đến ~3.~

Ngày thứ hai Chưng sẽ ăn những chiếc bánh còn lại.

Một hôm nọ Chưng đem cho Quýt một hộp bánh su kem rất ngon, nhưng chỉ ăn đơn thuần thôi thì lại rất nhàm chán vì vậy Quýt đã nghĩ ra một cách ăn để làm tăng độ ngon của những chiếc bánh. Cách ăn của Quýt chỉ đơn thuần là ghép nhiều chiếc bánh lại nhau và ăn trong một phát. Tuy nhiên là người làm nên những chiếc bánh nên Chưng biết có những chiếc bánh nếu ăn cùng nhau sẽ dẫn đến ngộ độc.

Măc dù đã ra sức cảnh báo nhưng Chưng vẫn không cách nào ngăn được Quýt, thật bất lưc....

Chưng cho Quýt hai danh sách thông tin, trong đó một danh sách là độ ngon của từng chiếc su kem được đánh số từ 1 đén n, danh sách còn lại là những chiếc su kem nếu ăn cùng với nhau sẽ dẫn đến tạch. Với thông tin được cung cấp Quýt quyết tâm tìm ra cách ghép để tạo nên chiếc bánh su kem ngon nhất và khi ăn vào sẽ không bị ngộ độc. Tuy là người đề xuất ý tưởng nhưng cậu ý cũng không biết cách ghép như thế nào là tối ưu vì vậy bạn hãy giúp cậu ấy nhé.

Input

• Dòng đầu tiên gồm hai số nguyên ~N, M~ với ~1 \le N \le 40~ và ~1 \le M \le 10^3~.

• Dòng tiếp theo gồm ~N~ số ~a_i~ đại diện cho độ ngon của từng chiếc bánh ~1 \le a_i \le 10^9~ .

• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u, v~ với ~1 \le u, v \le N~ và ~u \neq v~, mô tả nếu ăn su kem chỉ số ~u, v~ cùng lúc sẽ bị ngộ độc

Output

Độ ngon lớn nhất của chiếc bánh được tạo nên bằng cách ghép nhiều chiếc su kem khác lại với nhau và đảm bảo rằng khi ăn chiếc bánh đó sẽ không bị ngộ độc.

Sample Input 1

4 3
1 2 1 3
1 2
2 3
2 4

Sample Output 1

5

Giải thích:

Ta sẽ ghép các chiếc bánh vị trí 1, 3, 4 để đạt được độ ngon lớn nhất.

Chưng là một người đam mê su kem và cậu ấy đã tạo nên những chiếc su siêu ngon lành cho Quýt. Chưng đã sáng tạo ra ~26~ hương vị su kem khác nhau được kí hiệu là các chữ cái viết thường (~a-z~).

Một hôm nọ Chưng đã nấu thành công n chiếc bánh khác nhau và chuẩn bị đem qua nhà Quýt. Nhưng đối với Chưng thì bánh không chỉ ngon mà còn phải đẹp vì vậy cậu ấy đã quyết định ghép các su kem liên tiếp lại với nhau thành một su kem đối xứng.

Biết rằng su kem đối xứng là chuỗi các bánh liên tiếp với độ dài chẵn và ký hiệu hương vị của từng bánh khi ghép lại sẽ tạo thành 1 xâu đối xứng. Ngoài ra còn có một cách khác để tạo nên một su kem đối xứng là xu kem đó phải được ghép lại từ nhiều su kem đối xứng liên tiếp với kích thước nhỏ hơn.

VD: ~aa~, ~aabaab~ là những su kem đối xứng còn ~quyt~, ~chung~ thì không.

Vì lỡ nấu quá nhiều bánh nên Chưng không biết chọn ra một su kem đối xứng nào tặng cho Quýt. Bạn hãy giúp cậu ấy đếm xem có bao nhiêu cách tạo nên su kem đối xứng với n chiếc bánh có sẵn

Input

• Dòng đầu tiên gồm một số nguyên ~N~ với ~1 \le N \le 5.10^5~. Số lượng bánh su kem ban đầu được đánh số từ ~1~ đên ~n.~

• Dòng tiếp theo chứa ~n~ chữ cái trong đó chữ cái thứ ~i~ sẽ thuộc một trong 26 chữ cái tiếng Anh viết thường. Đại diện cho hương vị của từng chiếc bánh.

Output

Một dòng duy nhất là số cách tạo nên các su kem đối xứng từ các chiếc bánh đã cho.

Sample Input 1

6
abaaba

Sample Output 1

3

Giải thích:

Ta sẽ có các su kem đối xứng là: ~aa~, ~baab~ và ~abaaba~.