Huy có một dãy số ~a_1, a_2, ..., a_n~. Huy có thể thực hiện ~k~ lần biến đổi, mỗi lần Huy có thể thay đổi một chữ số trong dãy. Huy muốn tổng các số chia hết cho ~9~ trong dãy là lớn nhất có thể. Bạn hãy tìm cách để Huy có thể biến đổi dãy số thỏa mãn yêu cầu. Lưu ý rằng sau khi biến đổi có thể có một hoặc nhiều số bắt đầu bằng chữ số ~0~.

Dữ liệu - Nhập từ tệp văn bản DIV.inp:

• Dòng đầu tiên gồm hai số nguyên dương ~n, k~ ~(1 \le n \le 2000, 0 \le k \le 10000)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~.

Kết quả - Ghi ra tệp văn bản DIV.out:

• Một dòng duy nhất gồm tổng các số chia hết cho ~9~ trong dãy sau khi biến đổi.

Chấm điểm

Ví dụ

Dữ liệu (DIV.inp)

4 2
28 4 20 7

Kết quả (DIV.out)

117

Giải thích

Huy có thể thay đổi chữ số cuối cùng của phần tử đầu tiên thành chữ số ~7~, sau đó thay đổi chữ số đầu tiên của phần từ thứ ba thành chữ số ~9~ để được tổng ~27 + 90 = 117~. Có thể thấy đây là tổng lớn nhất có thể tạo được.