We're Going In

Time Limit
4s
Memory Limit
65536KB
Judge Program
Standard
Ratio(Solve/Submit)
0.00%(0/0)
Description:

As the standoff with Empire's Army continues, the Commander of Union, Yang, finally loses his patience. He intends to send a troop going through the long straight blockade line secretly and spying into enemy's activities.

After several days' observation, the Commander finds the following facts:

  • The blockade line is L meters long and there are N Empire's soldiers patrolling along the line.
  • The soldiers move one meter per second.
  • Each soldier's vision covers a range of R meters, both in front of and behind him.
  • When a soldier meets (the soldier meets, not his vision meets) an end of the line, he turns around and continues his patrol.

The whole break-through will last T seconds. To make sure the action successes, Yang wants to maximize the average uncovered length during the T seconds. In another word, assuming the function f(t) indicating the uncovered length of the blockade line at time t. Yang wants to maximize the definite integral:

I(x)=\int_{x}^{x+T} f(t)dt \qquad (x \geq 0)　

Input:

The first line of input contains four integers, L, R, N, T (0 ≤ L, R, T ≤ 1000000), (0 ≤ N ≤ 100).

The following N lines describe the soldiers. Each line consists of two integers, x (0 ≤ x ≤ L) and d. x indicates the initial position of the soldier and d indicates the direction of soldier's movement. The soldier moves to the end with x = L when d = 1 and to the end with x = 0 when d = -1.

Output:

Output the maximum I(x) with three digits after the decimal point.

Sample Input:
10 1 1 3
1 1
Sample Output:
25.000
Submit