【例题4】最大收益

题目描述

开始有 $n$ 个物品按从左到右 $1$ , $2$ , $\ldots$ , $n$ 的顺序排成一行，第 $i$ 个物品有一个代价 $a_i$ 和一个价值 $b_i$ 。

每次操作，你可以选择两个相邻的且代价之和不超过 $K$ 的物品，将它们从序列中删去，并获得两个物品价值之和的收益。

每次删去两个物品后，就认为这两个物品的左边和右边的就变成相邻的了。

现在你想知道，能获得收益之和的最大值是多少。

一行两个正整数 $n$ ， $K$ ，表示物品总数和代价之和的限制；

接下来 $n$ 行，第 $i$ 行两个正整数 $a_i$ ， $b_i$ ，代表第 $i$ 个物品的代价和价值。

一行一个整数，表示最大价值。