Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
We're Going In
Time Limit: 4000MSMemory Limit: 65536K
Total Submissions: 448Accepted: 28


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) 


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 the maximum I(x) with three digits after the decimal point.

Sample Input

10 1 1 3
1 1

Sample Output



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

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator