Boxing boxes

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1005;

int n, k;
ll w[maxn], h[maxn];
ll S[maxn], dp[maxn][maxn];


int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i) {
        scanf("%d%d", &w[i], &h[i]);
        S[i] = S[i - 1] + w[i];
    }

    dp[0][0] = 0;
    for(int i = 1; i <= n; ++i) dp[0][i] = 1e16;
    for(int i = 1; i <= k; ++i) {
        for(int j = 1; j <= n; ++j) {
            dp[i][j] = 1e16;

            ll mx = h[j];
            for(int t= j - 1; t >= 0; --t) {
                 mx=max(mx,h[t+1]);
                dp[i][j]=min(dp[i][j], dp[i - 1][t] + (S[j] - S[t]) * mx);
            }
        }
    }
    printf("%lld\n", dp[k][n]);
}