Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
We're Going In
 Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 448 Accepted: 28

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:

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 ≤ xL) 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

Source

[Submit]   [Go Back]   [Status]   [Discuss]