Cho ~N~ hàm tuyến tính ~f_1, f_2, \ldots, f_N~, trong đó ~f_i(x) = A_i x + B_i~.

Hãy tìm giá trị lớn nhất có thể của

~f_{p_1}\big(f_{p_2}\big(\cdots f_{p_K}(1) \cdots\big)\big)~

với ~p = (p_1, p_2, \ldots, p_K)~ là một dãy gồm ~K~ số nguyên phân biệt trong đoạn từ ~1~ đến ~N~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~.
• Dòng thứ ~i~ trong ~N~ dòng tiếp theo chứa hai số nguyên ~A_i~ và ~B_i~ — các hệ số của hàm ~f_i~.

Kết quả

In ra một số nguyên duy nhất là giá trị lớn nhất tìm được.

Ví dụ

Đầu vào:

3 2
2 3
1 5
4 2

Đầu ra:

26

Giải thích: Tất cả các dãy ~p~ có thể và giá trị ~f_{p_1}(f_{p_2}(1))~ tương ứng:

• ~p = (1, 2)~: ~f_1(f_2(1)) = 15~
• ~p = (1, 3)~: ~f_1(f_3(1)) = 15~
• ~p = (2, 1)~: ~f_2(f_1(1)) = 10~
• ~p = (2, 3)~: ~f_2(f_3(1)) = 11~
• ~p = (3, 1)~: ~f_3(f_1(1)) = 22~
• ~p = (3, 2)~: ~f_3(f_2(1)) = 26~

Giá trị lớn nhất là ~26~.

Đầu vào:

10 3
48 40
34 22
24 37
45 40
48 31
49 44
45 40
44 6
35 22
39 28

Đầu ra:

216223

Giới hạn

• ~1 \le N \le 2 \cdot 10^5~
• ~1 \le K \le \min(N, 10)~
• ~1 \le A_i, B_i \le 50~