Hoàng đang lạc ở một dãy núi và cần thoát ra khỏi nơi này. Dãy núi này gồm \(n+2\) đỉnh núi được đánh chỉ số từ \(0\) đến \(n+1\). Hoàng đang ở đỉnh núi \(0\) và cần di chuyển đến đỉnh núi \(n+1\) để đi cáp treo xuống núi. Vì các đỉnh núi gần nhau nên Hoàng có thể nhảy từ đỉnh núi \(i\) đến đỉnh núi \(j\) nếu \(0 < j-i \leq k\). Tuy nhiên, với mỗi đỉnh núi từ \(1\) đến \(n\), đỉnh núi thứ \(i\) có độ cao \(a_i\) và độ trơn trượt \(b_i\). Độ nguy hiểm của việc di chuyển từ đỉnh núi \(0\) đến đỉnh núi \(n+1\) là \(max(a_x)\times max(b_y)\) với \(x,y\) là chỉ số những đỉnh núi trong khoảng từ \(1\) đến \(n\) mà Hoàng nhảy đến. Nếu độ nguy hiểm quá cao, Hoàng sẽ bị trượt chân ngã xuống vách núi. Hãy giúp Hoàng tìm cách nhảy để có thể đến đỉnh núi \(n+1\) với độ nguy hiểm nhỏ nhất có thể.

Input

• 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, dòng thứ \(i\) chứa \(2\) số nguyên dương \(a_i,b_i\) \((1 \leq a_i, b_i \leq 10^9)\) miêu tả đỉnh núi thứ \(i\).

Output

• Độ nguy hiểm nhỏ nhất có thể để có thể đi đến đỉnh núi \(n+1\).

Scoring

• Subtask \(1\) (\(21\%\) số điểm): \(1 \leq n \leq 20\).
• Subtask \(2\) (\(23\%\) số điểm): \(1 \leq n,a_i \leq 100\).
• Subtask \(3\) (\(27\%\) số điểm): \(1 \leq n\leq 3000\).
• Subtask \(4\) (\(29\%\) số điểm): Không có điều kiên gì thêm.

Example

5 3
2 2
5 7
7 3
9 9
5 1

21

7 2
10 10
3 7
7 9
3 8
7 3
4 9
7 6

36