Goldilocks has a barn containing N cows (1 <= N <= 20,000). Her cows are rather sensitive to temperature.

Each cow i specifies a range of temperatures A(i)..B(i) that are "just right" (0 <= A(i) <= B(i) <= 1,000,000,000). If Goldilocks sets the thermostat to a temperature T < A(i), the cow will be too cold and will produce X units of milk. If she sets it to a temperature within the range (A(i) <= T <= B(i)), the cow will be comfortable and produce Y units of milk. If she sets it to T > B(i), the cow will be too hot and produce Z units of milk. The value of Y is always larger than both X and Z.

Given X, Y, and Z, as well as the preferred range of temperatures for each cow, please compute the maximum amount of milk Goldilocks can obtain if she sets the barn thermostat optimally. The values of X, Y, and Z are integers in the range 0..1000, and the thermostat can be set to any integer value.

Line 1: Four space-separated integers: N X Y Z.

Lines 2..1+N: Line 1+i contains two space-separated integers: A(i) and B(i).

The maximum amount of milk Goldilocks can obtain by an optimal temperature setting in her barn.

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > November > Bronze