A774.Rest Stops--Silver

普及+/提高

USACO

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

Farmer John and his personal trainer Bessie are hiking up Mount Vancowver. For
their purposes (and yours), the mountain can be represented as a long straight
trail of length LL meters (1L1061 \leq L \leq 10^6). Farmer John will hike the
trail at a constant travel rate of rFr_F seconds per meter (1rF1061 \leq r_F \leq 10^6). Since he is working on his stamina, he will not take any rest stops
along the way.
Bessie, however, is allowed to take rest stops, where she might find some
tasty grass. Of course, she cannot stop just anywhere! There are NN rest
stops along the trail (1N1051 \leq N \leq 10^5); the ii-th stop is xix_i meters
from the start of the trail (0<xi<L0 < x_i < L) and has a tastiness value cic_i
(1ci1061 \leq c_i \leq 10^6). If Bessie rests at stop ii for tt seconds, she
receives citc_i \cdot t tastiness units.
When not at a rest stop, Bessie will be hiking at a fixed travel rate of rBr_B
seconds per meter (1rB1061 \leq r_B \leq 10^6). Since Bessie is young and fit,
rBr_B is strictly less than rFr_F.
Bessie would like to maximize her consumption of tasty grass. But she is
worried about Farmer John; she thinks that if at any point along the hike she
is behind Farmer John on the trail, he might lose all motivation to continue!
Help Bessie find the maximum total tastiness units she can obtain while making
sure that Farmer John completes the hike.

输入格式

The first line of input contains four integers: LL, NN, rFr_F, and rBr_B.
The next NN lines describe the rest stops. For each ii between 11 and NN,
the i+1i+1-st line contains two integers xix_i and cic_i, describing the
position of the ii-th rest stop and the tastiness of the grass there.
It is guaranteed that rF>rBr_F > r_B, and $0 < x_1 < \dots < x_N < L $. Note
that rFr_F and rBr_B are given in seconds per meter!

输出格式

A single integer: the maximum total tastiness units Bessie can obtain.

输入输出样例

  • 输入#1

    10 2 4 3
    7 2
    8 1
    

    输出#1

    15
    

说明/提示

In this example, it is optimal for Bessie to stop for 77 seconds at the x=7x=7
rest stop (acquiring 1414 tastiness units) and then stop for an additional 11
second at the x=8x=8 rest stop (acquiring 11 more tastiness unit, for a total
of 1515 tastiness units).

首页