Chọn nhạc cho một đoạn phim quả thật không hề dễ dàng. Làm cách nào để ghép một đoạn nhạc 3 phút vào một đoạn phim 1 phút?

Rõ ràng ta phải cắt ngắn đoạn nhạc.Cho một đoạn nhạc gồm N ô nhịp, mỗi ô nhịp chứa đúng hai nốt nhạc. Ô nhịp thứ i chứa hai nốt nhạc với cao độ lần lượt là Ai và Bi.

Nhiệm vụ của bạn là tạo ra một đoạn nhạc mới gồm đúng M ô nhịp, bằng cách xóa đi một số ô nhịp trong đoạn nhạc cũ (sau khi xóa, các ô nhịp sẽđược dồn lại để lấp đầy khoảng trống, tuy nhiên thứ tự vẫn được giữ nguyên).

Đoạn nhạc mới phải thỏa mãn các yêu cầu sau:

• Ô nhịp đầu tiên và ô nhịp cuối cùng phải được giữ lại.

• Độ xấu của đoạn nhạc mới là bé nhất.

• Đoạn nhạc mới phải chứa đúng M ô nhịp.

Độ xấu của đoạn nhạc mới được định nghĩa bằng tổng độ xấu của các cặp ô nhịp liên tiếp. Độ xấu của hai ô nhịp liên tiếp được định nghĩa như sau:

• Nếu hai ô nhịp này vốn dĩ là hai ô nhịp kề nhau ở đoạn nhạc ban đầu, thì độ xấu bằng 0.

• Ngược lại, giả sử ô nhịp đầu tiên chứa hai nốt nhạc với cao độ lần lượt là X và Y , ô nhịp thứ hai chứa hai nốt nhạc với cao độ lần lượt là U và V , thì độ xấu bằng ~ (Y − U)^2 ~.

Ví dụ: Giả sử đoạn nhạc ban đầu là

(1, 1),(2, 2),(1, 1),(2, 2),(1, 1),(2, 2),(1, 2),(1, 1)

đoạn nhạc mới được lấy bằng cách xóa đi ô nhịp thứ hai và ô nhịp thứ ba

(1, 1),(2, 2),(1, 1),(2, 2),(1, 2),(1, 1)thì khi đó, độ xấu của đoạn nhạc mới là 1 + 0 + 0 + 0 + 0 = 1.

Tuy nhiên, nếu ta xóa đi ô nhịp thứ hai và ô nhịp thứ tư, ta sẽ thu được một đoạn nhạc mới với độ xấu bằng 0:

(1, 1),(1, 1),(1, 1),(2, 2),(1, 2),(1, 1)

Hãy tìm đoạn nhạc mới thỏa mãn đề bài và in ra độ xấu của đoạn nhạc đó.

Input

Dữ liệu gồm nhiều test case, số lượng test case có thể lên đến 20. Các test case được phân cách với nhau bởi một dòng trống.

Dữ liệu kết thúc bởi một dòng chứa hai số 0.

Mỗi test case có định dạng như sau:

• Dòng đầu tiên chứa hai số nguyên dương N và M, lần lượt là số lượng ô nhịp trong đoạn nhạc ban đầu và đoạn nhạc mới (2 ≤ M ≤ N ≤ 200).

• N dòng tiếp theo, dòng thứ i chứa hai số nguyên dương Ai và Bi, là cao độ của hai nốt nhạc trong ô nhịp thứ i của đoạn nhạc ban đầu (1 ≤ Ai, Bi ≤ 200)

Output

• Với mỗi test case, in ra độ xấu của đoạn nhạc mới tìm được.

Sample

Input #1

8 6
1 1
2 2
1 1
2 2
1 1
2 2
1 2
1 1
5 2
6 7
8 4
6 5
8 5
4 6
5 4
3 8
4 3
1 2
1 9
10 4
0 0

Output #1

0
9
4

Problem source: Free Contest thi thử HSG QG V2