Hệ tam phân (hay còn gọi là hệ cơ số 3) là hệ biểu diễn các số tự nhiên chỉ bằng các chữ số '~0~', '~1~', '~2~', dưới dạng tổng các lũy thừa của ~3~.

Số tam phân có ~m~ chữ số sẽ được biểu diễn dưới dạng "~c_{m-1}c_{m-2}...c_2c_1c_0~" với ~c_i \in \{0, 1, 2\}~. Số tam phân đó sẽ mang giá trị: $$c_{m-1} \times 3^{m-1} + c_{m-2} \times 3^{m-2} + ... + c_2 \times 3^2 + c_1 \times 3^1 + c_0 \times 3^0$$

Ví dụ: số tự nhiên ~5~ trong hệ thập phân sẽ được biểu diễn bằng số "~12~" (gồm ~2~ chữ số) trong hệ tam phân (vì ~5 = 1 \times 3^1+ 2 \times 3^0~); hoặc ngược lại, số có ~3~ chữ số là "~221~" trong hệ tam phân sẽ mang giá trị ~25~ trong hệ thập phân (vì ~25 = 2 \times 3^2 + 2 \times 3^1 + 1 \times 3^0~).

Cho mảng ~a~ gồm ~n~ phần tử là các số nguyên dương được biểu diễn dưới hệ thập phân.

Gọi ~f(x)~ là hàm trả về số lượng chữ số trong biểu diễn tam phân của ~x~, không tính những số ~0~ vô nghĩa ở đầu. Ví dụ: ~f(5) = 2~, ~f(25) = 3~.

Yêu cầu:

Tính giá trị nhỏ nhất có thể của ~f(a_i + a_j)~ (~\forall i,j: 1 \leq i, j \leq n~ và ~i \neq j~).

Input (vào từ TAMPHAN.INP)

• Dòng đầu chứa số nguyên dương ~n~ (~2 \leq n \leq 5 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ được biểu diễn dưới hệ thập phân, các số trên cùng một dòng cách nhau bởi dấu cách (~1 \leq a_i \leq 10^9~).

Output (xuất ra TAMPHAN.OUT)

• Gồm một số nguyên dương duy nhất là kết quả bài toán: giá trị nhỏ nhất có thể của ~f(a_i + a_j)~ (~\forall i,j: 1 \leq i, j \leq n~ và ~i \neq j~).

Ví dụ:

Sample Input 1

5
1 2 3 4 5

Sample Output 1

2

Note

• Khi chọn ~i = 1~, ~j = 3~, ta có ~a_1 + a_3 = 4~. Biểu diễn tam phân của ~4~ là "~11~", có ~2~ chữ số. Có thể chứng minh được không có lựa chọn tối ưu hơn (đáp án không thể bé hơn ~2~).

Subtask:

• ~20\%~ số test tương ứng với ~20\%~ số điểm có ~a_i + a_j < 9~ (~1 \leq i,j \leq n~ và ~i \neq j~).
• ~40\%~ số test tương ứng với ~40\%~ số điểm có ~n \leq 2000~.
• ~40\%~ số test còn lại tương ứng với ~40\%~ số điểm không có ràng buộc gì thêm.

Bác Hai là một người rất rộng lượng nên bác đã quyết định sẽ tặng quà cho mọi đứa trẻ trong xóm. Xóm bác gồm có ~n~ nhà được đánh dấu từ ~1~ đến ~n~, mỗi nhà đều có một đứa trẻ.

• Để thuận tiện, bác Hai sẽ tặng quà trong ~q~ lượt, mỗi lượt Bác tặng quà cho một dãy các ngôi nhà liên tiếp.
• Sau tất cả ~q~ lượt, các bạn nhỏ được tặng quà ít hơn bạn trong xóm mình (hoặc không được tặng quà) sẽ không hài lòng và tới nhà bác Hai để phàn nàn. Những bạn nhỏ không thuộc trường hợp trên sẽ được coi là đã hài lòng.

Vì bác muốn cho các bạn vui, bác Hai sẽ cố gắng đáp ứng yêu cầu của tất cả bạn trẻ, phát quà cho các bạn nhỏ cho đến khi tất cả mọi người đều hài lòng.

Yêu cầu:

Hãy giúp bác Hai tính số quà tặng ít nhất cần phát thêm, sau ~q~ lượt phát ban đầu, để làm cho các bạn nhỏ trong xóm hài lòng

Dữ liệu (Vào từ tệp GIFT.INP)

• Dòng đầu tiên chứa ~n~ và ~q~ lần lượt là là số ngôi nhà trong xóm và số lượt phát quà của bác Hai.
• ~q~ dòng tiếp theo chứa ~a~ và ~b~ là đại diện cho một lượt phát quà của bác Hai: bác phát từ ngôi nhà thứ ~a~ đến ngôi nhà thứ ~b~, mỗi nhà ~1~ phần quà (~1 \le a \le b \le n)~

Kết quả (Xuất ra tệp GIFT.OUT)

• In ra một số nguyên duy nhất là số lượng phần quà bác cần chuẩn bị thêm để tất cả những đứa trẻ trong xóm hài lòng.

Ví dụ:

Sample Input 1

5 3
1 2
1 3
3 5

Sample Output 1

2

Note

• Bác Hai đã phát quà cho các ngôi nhà theo thứ tự như trên.
• Ở mỗi ngôi nhà số phần quà bạn nhỏ nhận được là:

• Như vậy, đứa trẻ ở nhà số ~4~ và số ~5~ đã đến khiếu nại bác Hai, vì thế bác Hai cần phát thêm ~2~ phần quà, ~1~ cho nhà số ~4~ và ~1~ cho nhà số ~5~.

Subtask:

• ~20\%~ số test tương ứng với ~20\%~ số điểm có ~n \le 10^3, q \le 10^3~.
• ~40\%~ số test tương ứng với ~40\%~ số điểm có có ~n \le 10^5, q \le 10^5~.
• ~40\%~ số test tương ứng với ~40\%~ số điểm có có ~n \le 10^9, q \le 10^5~.

An đang tham gia một trò chơi điện tử bao gồm các màn diệt quái vật. Mỗi quái vật và siêu anh hùng trong trò chơi sẽ có ba đặc tính:

• Lượng máu (kí hiệu là ~h~).
• Sát thương tấn công (kí hiệu là ~a~).
• Phòng thủ (kí hiệu là ~d~).

Như vậy, một nhân vật có lượng máu là ~x~, sát thương tấn công là ~y~, khả năng phòng thủ là ~z~ sẽ được ký hiệu là ~(x,y,z)~. Một siêu anh hùng ~(u, v, w)~ sẽ chiến thắng quái vật ~(x,y,z)~ khi và chỉ khi cả ba điều kiện sau đều thỏa mãn:

• ~u \geq x~.
• ~v \geq y~.
• ~w \geq z~.

Bắt đầu mỗi màn, An sẽ nhận được các thông tin:

• ~n~ là số lượng quái vật có trong màn chơi.
• ~k~ là số quái vật ít nhất An cần phải chiến thắng để qua màn.
• ~n~ bộ ba ~(x,y,z)~ là đặc tính của từng con quái vật.

Trước khi chiến đấu, An cần phải xây dựng một siêu anh hùng ~(u,v,w)~ với chi phí là ~u+v+w~. Để qua màn, siêu anh hùng của An cần phải chiến thắng ít nhất ~k~ quái vật.

Yêu cầu:

Hãy giúp An xây dựng siêu anh hùng với chi phí thấp nhất sao cho An vẫn có thể qua màn.

Input (vào từ GAME.INP):

• Dòng đầu chứa hai số nguyên dương ~n~ và ~k~ (~1 \leq k \leq n \leq 5 \times 10^5~).
• ~n~ dòng tiếp theo, mỗi dòng chứa bộ ba số nguyên ~x,y,z~ cách nhau bởi dấu cách (~1 \leq x,y,z \leq 300~).

Output (xuất ra GAME.OUT):

• Gồm một số nguyên dương là chi phí thấp nhất để An có thể vượt qua màn.

Ví dụ:

Sample Input 1

3 2
1 2 3
4 5 1
3 1 4

Sample Output 1

9

Note

• An sẽ xây dựng siêu anh hùng ~(3, 2, 4)~ với chi phí là ~3+2+4=9~. Siêu anh hùng này sẽ chiến thắng được quái vật ~(1,2,3)~ và ~(3,1,4)~.

Subtask:

• ~10\%~ số test tương ứng với ~10\%~ số điểm có ~k = n~.
• ~30\%~ số test tương ứng với ~30\%~ số điểm có ~x,y,z \leq 100~ và ~n \leq 100~.
• ~30\%~ số test tương ứng với ~30\%~ số điểm có ~z = 1~ với tất cả ~n~ quái vật.
• ~30\%~ số test tương ứng với ~30\%~ số điểm không có ràng buộc gì thêm.