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 các bạn. Tiểu Chưng đã làm tổng cộng ~N~ chiếc bánh su kem, được đánh số từ ~1~ đến ~N~.Ban đầu, các bánh có cùng hương vị sẽ được xếp chung một hộp. Dữ liệu đầu vào cho biết mối quan hệ này: ~M~ cặp bánh ~u, v~ được xếp chung hộp.

Lưu ý: Các bánh chung hộp tạo thành một tập hợp liên thông (Thành phần liên thông). Mỗi tập hợp các bánh này chính là một hộp.Ví dụ: Nếu ~1, 2~ chung hộp và ~2, 3~ chung hộp, thì ~1, 2, 3~ sẽ nằm chung ~1~ hộp. Các bánh không được nhắc đến sẽ nằm riêng ~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 các bạn 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ẽ gộp những hộp bánh lại với nhau để 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.

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, Chưng mang tặng bạn một hộp bánh su kem rất ngon. Tuy nhiên, ăn từng chiếc một thì thật là nhàm chán, nên bạn nảy ra một ý tưởng thú vị: ghép nhiều chiếc bánh lại rồi ăn một lần để tăng độ ngon.

Tuy nhiên, vì là người làm ra bánh, Chưng biết rằng có những cặp bánh nếu ăn cùng nhau sẽ gây ngộ độc. Dù Chưng đã cố gắng cảnh báo, bạn vẫn bất chấp, quyết tâm thử cho bằng được. Bạn được cho hai danh sách thông tin:

• Danh sách thứ nhất: độ ngon của từng chiếc bánh su kem, được đánh số từ ~1~ đến ~N~.
• Danh sách thứ hai: các cặp bánh không thể ăn cùng nhau, vì nếu ghép chung sẽ bị tạch.

Giờ đây, bạn muốn chọn ra một nhóm bánh để ăn cùng lúc sao cho:

Tổng độ ngon là lớn nhất. và không có hai bánh nào trong nhóm gây ngộ độc khi ăn cùng.

Bạn hãy tìm ra tổng độ ngon lớn nhất mà bạn có thể đạt được!

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~.