Eating Cheese#569
At the cheese factory in Flatland, mice reside who love cheese and often deplete the cheese stocks prepared for store delivery.
There are mice living at the factory. For the -th mouse, its cheese-eating speed s_i is known, meaning the mouse can eat s_i grams of cheese per hour.
Recently, the mice learned of the factory's production schedule. cheese wheels are planned to be produced. For each wheel, the following details are known: r_i — the beginning of the hour at which it will be ready, d_i — the beginning of the hour at which it will start to spoil, and p_i — the weight of the wheel in grams.
The mice have decided to eat all the cheese. At any given moment, each mouse can eat some cheese wheel. Mice are fastidious creatures: no more than one mouse can eat the same wheel at any given time. However, at any moment, a mouse may stop eating one wheel and start eating another, even a wheel previously eaten by another mouse.
Mice dislike eating cheese after it starts to spoil, but they cannot leave any cheese uneaten. They want to arrange the eating so that the value , which is the maximum number of hours any wheel is still being eaten after it starts to spoil, is minimized. Help the mice organize cheese eating in this way.
The first line contains two integers and (1 \le n, m \le 30). The next lines describe the cheese wheels: each contains three integers p_i, r_i, d_i (1 \le p_i \le 10^5, 0 \le r_i < d_i \le 10^7). Then lines follow, each containing an integer s_j (1 \le s_j \le 10^5).
Print one real number — the sought minimum . The answer must be printed with at least 10^{-4} precision.
Example 1
Explanation of the example
In the first example, the mice should organize their cheese eating as follows. First, the first mouse starts eating the first wheel. When the second wheel appears, it stops eating the first and starts eating the second (at this point, grams remain on the first wheel). The second mouse then eats the first wheel. After hours, the first mouse finishes the second wheel ( hours after it starts to spoil) and returns to the first; by this time, the second mouse has eaten another grams from the first and grams remain. Thus, after another hour, the first mouse finishes the first wheel, again hours after it starts to spoil.
In the second example, the mouse manages to finish eating the cheese before it starts to spoil.