Goldilocks and the N Cows

The story of Goldilocks and the three bears is well known. Much less known is that Goldilocks eventually took up farming. On her farm she has a barn holding $N$ cows ($1 \le N \le 20000$), and those cows are sensitive to temperature.

Each cow $i$ has a range of temperatures $A_i$ through $B_i$ that feels just right to it ($0 \le A_i \le B_i \le 10^9$). If Goldilocks sets the barn thermostat to a temperature $T < A_i$, cow $i$ is too cold and produces $X$ units of milk. If she sets it to a temperature with $A_i \le T \le B_i$, the cow is comfortable and produces $Y$ units of milk. If she sets it to a temperature $T > B_i$, the cow is too hot and produces $Z$ units of milk. $Y$ is always larger than $X$ and also larger than $Z$.

Given $X$, $Y$, $Z$ and the preferred range of every cow, compute the maximum amount of milk Goldilocks can obtain when she sets the thermostat to the best possible value. $X$, $Y$ and $Z$ are integers between $0$ and $1000$, and the thermostat can be set to any integer value.

• Line 1: four space-separated integers $N$, $X$, $Y$, $Z$.
• Lines 2 through $1+N$: line $1+i$ contains the two space-separated integers $A_i$ and $B_i$ of cow $i$.

• Line 1: the maximum amount of milk Goldilocks obtains when the barn temperature is set to the best possible value.

In the first example the barn holds four cows, whose preferred ranges are 5 through 8, 3 through 4, 13 through 20, and 7 through 10. A cold cow produces 7 units of milk, a comfortable cow produces 9, and a hot cow produces 6.

Setting the thermostat to 7 or to 8 leaves cows 1 and 4 comfortable, cow 2 too hot, and cow 3 too cold. The milk adds up to 31 units.