#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1);
const long long nax = 1e5 + 10, mod = 998244353, inf = 1e18;
template <class T, class U>
T lstTrue(T lo, T hi, U first) {
  lo--;
  assert(lo <= hi);
  while (lo < hi) {
    T mid = lo + (hi - lo + 1) / 2;
    first(mid) ? lo = mid : hi = mid - 1;
  }
  return lo;
}
pair<long long, long long> operator-(const pair<long long, long long>& l,
                                     const pair<long long, long long>& r) {
  return pair<long long, long long>(l.first - r.first, l.second - r.second);
}
long long cross(const pair<long long, long long>& a,
                const pair<long long, long long>& b) {
  return a.first * b.second - a.second * b.first;
}
long long cross(const pair<long long, long long>& p,
                const pair<long long, long long>& a,
                const pair<long long, long long>& b) {
  return cross(a - p, b - p);
}
long long need[200][200], mn, n, k;
vector<pair<long long, long long> > a;
pair<long long, long long> dp[200][200];
bool pos(long long x) {
  mn = x;
  for (long long i = n - 1; i >= 0; i--)
    for (long long j = i + 1; j < n; j++) dp[i][j] = {};
  for (long long i = n - 1; i >= 0; i--)
    for (long long j = i + 1; j < n; j++)
      for (long long kk = i + 1; kk < j; kk++) {
        long long tot = dp[i][kk].first + dp[kk][j].first;
        long long to = dp[i][kk].second + dp[kk][j].second;
        to += cross(a[i], a[kk], a[j]);
        if (to >= mn) {
          ++tot;
          to = 0;
        }
        dp[i][j] = max(dp[i][j], make_pair(tot, to));
      }
  return dp[0][n - 1].first >= k + 1;
}
void solve() {
  cin >> n >> k;
  a.resize(n);
  for (long long i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
  cout << (lstTrue(0LL, inf, [&](long long x) { return pos(x); }));
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  long long tt = 1;
  for (long long i = 1; i <= tt; i++) {
    solve();
  }
  return 0;
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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;
const double PI = acos(-1);
const long long nax = 1e5 + 10, mod = 998244353, inf = 1e18;
template <class T, class U>
T lstTrue(T lo, T hi, U first) {
  lo--;
  assert(lo <= hi);
  while (lo < hi) {
    T mid = lo + (hi - lo + 1) / 2;
    first(mid) ? lo = mid : hi = mid - 1;
  }
  return lo;
}
pair<long long, long long> operator-(const pair<long long, long long>& l,
                                     const pair<long long, long long>& r) {
  return pair<long long, long long>(l.first - r.first, l.second - r.second);
}
long long cross(const pair<long long, long long>& a,
                const pair<long long, long long>& b) {
  return a.first * b.second - a.second * b.first;
}
long long cross(const pair<long long, long long>& p,
                const pair<long long, long long>& a,
                const pair<long long, long long>& b) {
  return cross(a - p, b - p);
}
long long need[200][200], mn, n, k;
vector<pair<long long, long long> > a;
pair<long long, long long> dp[200][200];
bool pos(long long x) {
  mn = x;
  for (long long i = n - 1; i >= 0; i--)
    for (long long j = i + 1; j < n; j++) dp[i][j] = {};
  for (long long i = n - 1; i >= 0; i--)
    for (long long j = i + 1; j < n; j++)
      for (long long kk = i + 1; kk < j; kk++) {
        long long tot = dp[i][kk].first + dp[kk][j].first;
        long long to = dp[i][kk].second + dp[kk][j].second;
        to += cross(a[i], a[kk], a[j]);
        if (to >= mn) {
          ++tot;
          to = 0;
        }
        dp[i][j] = max(dp[i][j], make_pair(tot, to));
      }
  return dp[0][n - 1].first >= k + 1;
}
void solve() {
  cin >> n >> k;
  a.resize(n);
  for (long long i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
  cout << (lstTrue(0LL, inf, [&](long long x) { return pos(x); }));
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  long long tt = 1;
  for (long long i = 1; i <= tt; i++) {
    solve();
  }
  return 0;
}

```