Có \(n\) người, người thứ \(i\) \((1 \le i \le n)\) được gán một số nguyên \(a_i\) (\(|a_i| \le 10^5 \)), người ta muốn chọn ra \(3 \times k\) người chia thành \(k\) nhóm, mỗi nhóm gồm ba người. Sự hợp tác của một nhóm gồm ba người được tính bằng tích các số gán cho ba người đó, cụ thể nếu ba người \(i_1, i_2, i_3 (1 \le i_1, i_2, i_3 \le n)\) được xếp vào một nhóm thì sự hợp tác được tính bằng \(a_{i_1} \times a_{i_2} \times a_{i_3}\) .

Yêu cầu: Hãy tìm cách chọn \(k\) nhóm để tổng sự hợp tác của \(k\) nhóm là lớn nhất.

Dữ liệu: Vào từ thiết bị nhập chuẩn theo khuôn dạng:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2 ..., a_n\).

Kết quả: một số nguyên là tổng sự hợp tác của \(k\) nhóm.

Ràng buộc:

• Có 10% số lượng test ứng với 10% số điểm có \(k=1; n \le 10\).
• Có 20% số lượng test ứng với 20% số điểm có \(k=1; n \le 10^5\).
• Có 20% số lượng test ứng với 20% số điểm có \(k=2; n \le 10\).
• Có 10% số lượng test ứng với 10% số điểm có \(k=2; n \le 10^5\).
• Có 20% số lượng test ứng với 20% số điểm có \(k = 3; n \le 10^5\).
• Có 20% số lượng test ứng với 20% số điểm có \(k \le 5; n \le 10^5\).

Input

9 2
1 2 3 4 -2 6 7 8 -9

Output

408

Giải thích

8*7*6 + 4*(-9)*(-2) = 408