17905번 - Expecting Rain 스페셜 저지다국어

The Bluewater Geocloud Organization (BGO) has recently developed brand new software able to predict with pinpoint precision at which second any particular cloud will start and stop raining, and with what intensity. There is, however, some uncertainty about how a cloud will move around; for each zip code, each cloud will be over that zip code with some probability.

You have scraped some information about your zip code from the BGO website, and want to use it to plan your walk to the bus stop. You wish to minimize the expected amount of rain that would fall on you. To reach the bus you must get to the bus stop within t seconds from now. You have timed your walking speed to be exactly 1m/s.

To complicate matters, some parts of the walk to the bus are covered by roofs where it might be beneficial to make shorts breaks whilst waiting for the worst rain to pass. Your front door (at d meters from the bus stop) is always under a roof – but the bus stop need not be.

The first line of input is four space-separated integers: d (1 ≤ d ≤ 1 000), the distance to the bus stop in meters, t (d ≤ t ≤ 10 000) the time until the bus leaves, c (0 ≤ c ≤ 1 000 000), the number of clouds tracked by BGO, and finally r (0 ≤ r ≤ d), the number of roofs. The next c lines describe the clouds; the i’th such line contains four numbers s_i, e_i, p_i and a_i describing the i’th cloud:

• s_i (0 ≤ s_i < t) is an integer giving the number of seconds until the cloud starts its raining period,
• e_i (si < e_i ≤ t) is an integer giving the number of seconds until the cloud ends its raining period,
• p_i (0 ≤ p_i ≤ 1) is a real number (with at most 6 digits after the decimal point) giving the probability that the cloud is in your zip code during its raining period, and
• a_i (0 ≤ a_i ≤ 100) is an integer indicating the amount of rain the cloud will release during its raining period, given as nm per second.

Finally r roof segments follow, each on its own line; the j’th such line contains two integers x_j and y_j (0 ≤ x_j < y_j ≤ d + 1), indicating that there is a roof segment starting at distance x_j away from home, ending at distance y_j away from home along the route to the bus stop. Both your home, the bus stop an the entire route between them are in the same zip code. No two roofs overlap, however one roof may start at the same exact location as another ends.

The output consists of single a real value, the minimum amount of rain in nm you can expect on your route if you reach the bus stop in time. Answers with absolute or relative precision 10⁻⁵ of the actual value will be accepted.