Bài tập

Một xưởng cưa tính tiền cắt gỗ theo chiều dài của thanh đang được cắt: mỗi nhát cắt tốn số tiền bằng chiều dài của đoạn gỗ chứa nhát cắt đó, và mỗi lần chỉ cắt được một nhát.

Cho một thanh gỗ dài \(L\) mét và \(n\) vị trí cần cắt (tính từ một đầu thanh). Thứ tự thực hiện các nhát cắt ảnh hưởng đến tổng chi phí. Ví dụ, thanh dài \(10\) cần cắt ở \(2, 4, 7\): cắt lần lượt \(2 \to 4 \to 7\) tốn \(10 + 8 + 6 = 24\), còn cắt \(4 \to 2 \to 7\) tốn \(10 + 4 + 6 = 20\).

Hãy tính tổng chi phí nhỏ nhất để cắt thanh gỗ tại đủ \(n\) vị trí đã cho.

Input

Dữ liệu gồm nhiều bộ test. Mỗi bộ test gồm:

• dòng thứ nhất: số nguyên \(L\) (chiều dài thanh);
• dòng thứ hai: số nguyên \(n\) (số vị trí cắt);
• dòng thứ ba: \(n\) số nguyên \(c_1 < c_2 < \dots < c_n\), các vị trí cần cắt.

Dữ liệu kết thúc bằng một dòng chứa \(L = 0\) (không phải bộ test).

Output

Với mỗi bộ test in ra trên một dòng chi phí nhỏ nhất.

Constraints

• \(2 \le L \le 999\)
• \(1 \le n \le 49\), \(0 < c_i < L\), dãy \(c\) tăng ngặt
• Có không quá \(100\) bộ test.

Sample Input

20
3
5 8 14
9
4
2 3 5 7
0

Sample Output

40
21

Explanation

Với bộ đầu tiên: cắt tại \(8\) trước (tốn \(20\)), đoạn \([0,8]\) cắt tại \(5\) (tốn \(8\)), đoạn \([8,20]\) cắt tại \(14\) (tốn \(12\)); tổng \(40\).

Một cấp số cộng là dãy số mà hiệu của hai phần tử liên tiếp luôn bằng một hằng số \(D\) gọi là công sai. Ví dụ \(3, 5, 7, 9\) là cấp số cộng với công sai \(2\).

Cho dãy \(A\) gồm \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\). Ta chọn một số phần tử của \(A\), giữ nguyên thứ tự xuất hiện (dãy con, các vị trí không cần liền kề) sao cho dãy con nhận được \(B_1, B_2, \dots, B_k\) thoả mãn \(B_i = B_{i-1} + D\) với mọi \(i \ge 2\). Công sai \(D\) do bạn tự chọn trong khoảng \(1 \le D \le 50\).

Hãy tìm độ dài lớn nhất \(k\) của một dãy con như vậy (dãy con chỉ có một phần tử luôn thoả mãn).

Input

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\).

Output

In ra một số nguyên là độ dài lớn nhất của dãy con là cấp số cộng với công sai \(D \in [1, 50]\).

Constraints

• \(1 \le N \le 2000\)
• \(1 \le a_i \le 10^9\)

Sample Input

9
4 21 6 15 8 33 10 12 3

Sample Output

5

Explanation

Chọn \(D = 2\) và dãy con \(4, 6, 8, 10, 12\) (các phần tử còn lại bị bỏ qua), độ dài \(5\). Không có cách nào dài hơn.

Cho dãy số nguyên dương \(A = (a_1, a_2, \dots, a_N)\). Một dãy con của \(A\) là dãy thu được bằng cách xoá đi một số phần tử (có thể không xoá) và giữ nguyên thứ tự các phần tử còn lại.

Một dãy con \(b_1, b_2, \dots, b_k\) được gọi là cấp số cộng công sai \(D\) nếu \(b_{t+1} - b_t = D\) với mọi \(1 \le t < k\). Dãy con chỉ có một phần tử luôn thoả mãn với mọi \(D\).

Bạn được tự do chọn một công sai nguyên \(D\) với \(1 \le D \le 50\). Hãy tìm độ dài lớn nhất của một dãy con của \(A\) là cấp số cộng với công sai \(D\) đã chọn.

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\).

Output

• In ra một số nguyên duy nhất: độ dài lớn nhất tìm được.

Constraints

• \(1 \le N \le 10^5\)
• \(1 \le a_i \le 10^9\)

Sample Input

10
4 9 6 8 10 12 14 3 16 18

Sample Output

8

Explanation

Chọn \(D = 2\), dãy con \(4, 6, 8, 10, 12, 14, 16, 18\) gồm \(8\) phần tử là một cấp số cộng công sai \(2\). Không có cách nào dài hơn.

Cho số nguyên dương \(N\). Liệt kê tất cả các cặp \((A, B)\) với \(1 \le A \le B \le N\) sao cho \(A^2 + B^2\) là một số chính phương.

Input

Một số nguyên \(N\).

Output

Mỗi dòng in một cặp \(A\ B\) (cách nhau một dấu cách), các cặp sắp xếp theo thứ tự từ điển (tăng dần theo \(A\), cùng \(A\) thì tăng dần theo \(B\)). Nếu không có cặp nào thì không in gì.

Constraints

• \(1 \le N \le 10^4\)

Sample Input

17

Sample Output

3 4
5 12
6 8
8 15
9 12
12 16