```c
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 55,INF = 0x3f3f3f3f;
int n,s[N],sum[N],f[N][N][2],m;
void solve()
{
for(int len=2;len<=n;len++)
for(int l=1;l+len-1<=n;l++)
{
int r = l+len-1;
int a = f[l+1][r][0]+(s[l+1]-s[l])*(sum[l]+sum[n]-sum[r]);
int b = f[l+1][r][1]+(s[r]-s[l])*(sum[l]+sum[n]-sum[r]);
f[l][r][0] = min(a,b);
int c = f[l][r-1][0]+(s[r]-s[l])*(sum[l-1]+sum[n]-sum[r-1]);
int d = f[l][r-1][1]+(s[r]-s[r-1])*(sum[l-1]+sum[n]-sum[r-1]);
f[l][r][1] = min(c,d);
}
}
int main()
{
scanf("%d%d",&n,&m);
memset(f,0x3f,sizeof f);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&s[i],&sum[i]);
sum[i]+=sum[i-1];
}
f[m][m][0] = f[m][m][1] = 0;
solve();
printf("%d\n",min(f[1][n][0],f[1][n][1]));
return 0;
}
```
by 123huchenghao @ 2024-06-29 13:34:18