#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, rlj, k, nxt, cur, len, res, x[444], y[444], mx[202][202];
long long le, ri, mid, s[202][202], f[202][202];
long long cross(long long xa, long long ya, long long xb, long long yb) {
  return abs(xa * yb - ya * xb);
}
long long cross(int i, int j, int k) {
  return cross(x[j] - x[i], y[j] - y[i], x[k] - x[i], y[k] - y[i]);
}
void tryupd(int i, int j, int v, long long s) {
  if (v > mx[i][j] || (v == mx[i][j] && s < f[i][j])) {
    mx[i][j] = v;
    f[i][j] = s;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (i = 0; i < n; i++) {
    scanf("%d%d", &x[i], &y[i]);
    x[i + n] = x[i];
    y[i + n] = y[i];
  }
  for (i = 0; i < n; i++)
    for (len = 2; len < n; len++)
      s[i][len] = s[i][len - 1] + cross(i, i + len - 1, i + len);
  le = 0;
  ri = s[0][len - 1];
  while (le < ri) {
    mid = (le + ri) / 2 + 1;
    res = 0;
    for (len = 2; len + 1 < n && res < m; len++)
      for (i = 0; i < n; i++) {
        mx[i][len] = 0;
        f[i][len] = 0;
        j = i + len;
        rlj = j % n;
        if (s[i][len] >= mid && s[rlj][n - len] >= mid) {
          mx[i][len] = 1;
          f[i][len] = s[i][len];
          tryupd(i, len, mx[i][len - 1], f[i][len - 1]);
          nxt = i + 1;
          if (nxt >= n) nxt -= n;
          tryupd(i, len, mx[nxt][len - 1], f[nxt][len - 1]);
          cur = nxt + 1;
          for (k = 2; len - k >= 2; k++, cur++) {
            if (cur >= n) cur -= n;
            tryupd(i, len, mx[i][k] + mx[cur][len - k],
                   f[i][k] + f[cur][len - k]);
          }
          if (s[i][len] - f[i][len] >= mid) {
            ++mx[i][len];
            f[i][len] = s[i][len];
          }
          if (mx[i][len] > res) res = mx[i][len];
        }
      }
    if (res >= m)
      le = mid;
    else
      ri = mid - 1;
  }
  printf("%lld\n", ri);
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

You are given a strictly convex polygon with n vertices.

You will make k cuts that meet the following conditions: 

  * each cut is a segment that connects two different nonadjacent vertices; 
  * two cuts can intersect only at vertices of the polygon. 



Your task is to maximize the area of the smallest region that will be formed by the polygon and those k cuts.

Input

The first line contains two integers n, k (3 ≤ n ≤ 200, 0 ≤ k ≤ n-3).

The following n lines describe vertices of the polygon in anticlockwise direction. The i-th line contains two integers x_i, y_i (|x_i|, |y_i| ≤ 10^8) — the coordinates of the i-th vertex.

It is guaranteed that the polygon is convex and that no two adjacent sides are parallel.

Output

Print one integer: the maximum possible area of the smallest region after making k cuts multiplied by 2.

Examples

Input


8 4
-2 -4
2 -2
4 2
1 5
0 5
-4 4
-5 0
-5 -1


Output


11


Input


6 3
2 -2
2 -1
1 2
0 2
-2 1
-1 0


Output


3

Note

In the first example, it's optimal to make cuts between the following pairs of vertices: 

  * (-2, -4) and (4, 2), 
  * (-2, -4) and (1, 5), 
  * (-5, -1) and (1, 5), 
  * (-5, 0) and (0, 5). 

<image> Points (-5, -1), (1, 5), (0, 5), (-5, 0) determine the smallest region with double area of 11. 

In the second example, it's optimal to make cuts between the following pairs of vertices: 

  * (2, -1) and (0, 2), 
  * (2, -1) and (1, 0), 
  * (-1, 0) and (0, 2). 

<image> Points (2, -2), (2, -1), (-1, 0) determine one of the smallest regions with double area of 3. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, rlj, k, nxt, cur, len, res, x[444], y[444], mx[202][202];
long long le, ri, mid, s[202][202], f[202][202];
long long cross(long long xa, long long ya, long long xb, long long yb) {
  return abs(xa * yb - ya * xb);
}
long long cross(int i, int j, int k) {
  return cross(x[j] - x[i], y[j] - y[i], x[k] - x[i], y[k] - y[i]);
}
void tryupd(int i, int j, int v, long long s) {
  if (v > mx[i][j] || (v == mx[i][j] && s < f[i][j])) {
    mx[i][j] = v;
    f[i][j] = s;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (i = 0; i < n; i++) {
    scanf("%d%d", &x[i], &y[i]);
    x[i + n] = x[i];
    y[i + n] = y[i];
  }
  for (i = 0; i < n; i++)
    for (len = 2; len < n; len++)
      s[i][len] = s[i][len - 1] + cross(i, i + len - 1, i + len);
  le = 0;
  ri = s[0][len - 1];
  while (le < ri) {
    mid = (le + ri) / 2 + 1;
    res = 0;
    for (len = 2; len + 1 < n && res < m; len++)
      for (i = 0; i < n; i++) {
        mx[i][len] = 0;
        f[i][len] = 0;
        j = i + len;
        rlj = j % n;
        if (s[i][len] >= mid && s[rlj][n - len] >= mid) {
          mx[i][len] = 1;
          f[i][len] = s[i][len];
          tryupd(i, len, mx[i][len - 1], f[i][len - 1]);
          nxt = i + 1;
          if (nxt >= n) nxt -= n;
          tryupd(i, len, mx[nxt][len - 1], f[nxt][len - 1]);
          cur = nxt + 1;
          for (k = 2; len - k >= 2; k++, cur++) {
            if (cur >= n) cur -= n;
            tryupd(i, len, mx[i][k] + mx[cur][len - k],
                   f[i][k] + f[cur][len - k]);
          }
          if (s[i][len] - f[i][len] >= mid) {
            ++mx[i][len];
            f[i][len] = s[i][len];
          }
          if (mx[i][len] > res) res = mx[i][len];
        }
      }
    if (res >= m)
      le = mid;
    else
      ri = mid - 1;
  }
  printf("%lld\n", ri);
  return 0;
}

```