农场的冬天到了,这意味着下雪了!从农舍到谷仓的路上有 N 块地砖,方便地编号为 1 \dots N,第 i 块地砖上覆盖了 f_i 英尺的雪。
Farmer John 从第 1 块地砖出发,必须到达第 N 块地砖去叫醒奶牛。第 1 块地砖被农舍的屋顶遮蔽,第 N 块地砖被谷仓的屋顶遮蔽,因此这两块地砖上没有雪。但要踩在其他地砖上,Farmer John 需要穿靴子!
在他的恶劣天气背包中,Farmer John 有 B 双靴子,编号为 1 \dots B。有些靴子比其他靴子更耐用,有些靴子比其他靴子更灵活。具体来说,第 i 双靴子允许 Farmer John 在最多 s_i 英尺深的雪中行走,并且每步最多可以移动 d_i 块地砖。
不幸的是,靴子的打包方式使得 Farmer John 在任何时候只能访问最上面的一双靴子。因此,Farmer John 可以随时穿上最上面的一双靴子(丢弃旧靴子)或丢弃最上面的一双靴子(使下一双靴子可访问)。
Farmer John 只能在地砖上更换靴子。如果该地砖上有 f 英尺的雪,那么他脱下的靴子和穿上的靴子都必须能够承受至少 f 英尺的雪。他丢弃但未穿过的中间靴子不需要满足此限制。
请帮助 Farmer John 最小化浪费,确定他到达谷仓需要丢弃的最少靴子对数。假设 Farmer John 最初没有穿任何靴子。