#1406. Claes的华山之旅

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Claes

题目描述

不到华山非好汉。

Claes打算前往华山旅游。但连日来的学习耗尽了她的精力。现在,她只剩下了点精力值。

简单起见,我们假设登山道单调上升。Claes可以从山脚(海拔为0)开始爬,也可以直接坐北峰缆车前往海拔为处。由于Claes认为“真男人不会走回头路”,她只会一直往上爬,之后从山顶坐西峰缆车下山。得益于从小爬山的经历,Claes爬山只消耗体力,不消耗精力。

华山有个景点。每个景点都有一个精彩度与一个费力度。Claes欣赏第个景点,就要花费费力度的精力值,看到精彩度的风景。坐缆车时,由于只需要坐着看风景,所以不需要花费精力值就能收获精彩度为的风景。需要注意的是,第个景点在海拔为

现在,Claes想知道她能看见的风景精彩度之和最高为多少。

输入格式

第一行四个整数。

第二到行,第行三个整数

输出格式

一个整数,Claes想能看见的风景精彩度之和的最大值。

样例

样例输入

10 10 6 100
1 7
2 11
1 9
2 18
1 5
2 7
99 1
1 12
2 13
9 15

样例输入

132

样例解释

Claes先坐缆车前往海拔为6的景点,并在缆车上欣赏到精彩度为100的风景。

接着,Claes会游览海拔为6、8、9处的景点,共消耗5点精力,欣赏到精彩度共计为32的风景。

数据范围与提示

保证答案在int范围内