Farmer John 闲来无事的时候总喜欢坐下来看书。这些年来，他一共收集了 本书（），他打算搭一个新的书架来装这些书。
每本书都有个宽度 和高度 ，书必须按顺序来摆放（即同一层书架摆的书必须是连续的一个区间）。每层书架的总宽度不能超过 （），每层书架的高度等于这一层最高的书的高度，整个书架的高度等于每层书架的高度之和。
现在请你帮 FJ 求出书架高度的最小值。
第一行两个整数 。
接下来 行，每行两个整数 （，）。
输出一个整数，书架高度最小值。
5 10 5 7 9 2 8 5 13 2 3 8
21
第一层放第一本书，第二层放第二，三，四本书，第三层放第五本书，总高度为 ，可以证明不存在更优的方案。