3587: 商品库存交易挑战

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:15 解决:7

题目描述

小杨经营一家商店,未来 n 天中,每天都会提供一种商品的买入价 bi卖出价 si(保证 sibi)。

他每天可以选择以下操作之一:

  • 买入 1 件商品(前提:当前库存 < 最大库存 K
  • 卖出 1 件商品(前提:当前库存 > 0)
  • 不操作

每天只能进行一次操作。

目标:在 n 天结束后,获得最大总利润(利润 = 所有卖出收入 - 所有买入支出)。

初始库存为 0,最终库存无限制(可以有剩余商品)。

请你帮助小杨计算他能获得的最大利润

给定 n 天的买入价 bi、卖出价 si,以及最大库存容量 K,求最大利润。


输入

  • 第一行:两个整数 n,K1n5000,1K100
    • n:天数
    • K:最大库存容量(每天最多持有 K 件商品)
  • 接下来 n 行:每行两个整数 bi,si
    • 1bisi104

输出

一个整数,表示最大可能利润。

样例输入 复制

3 1
1 3
2 5
4 6

样例输出 复制

5

提示

变量 范围 说明
n 1n5000 天数
K 1K100 最大库存
bi,si 1bisi104 价格