Eating Cheese
At the cheese factory in Flatland, a group of mice resides. These mice are fond of cheese and frequently deplete the cheese stocks intended for store delivery.
There are m mice living at the factory. Each mouse, indexed as i, has a known cheese-eating speed s_i, indicating the number of grams of cheese it can consume per hour.
Recently, the mice discovered the factory's production schedule. The plan is to produce n cheese wheels. For each wheel, the following details are known: r_i - the hour it will be ready, d_i - the hour it will begin to spoil, and p_i - the weight of the cheese wheel in grams.
The mice have decided to consume all the cheese. At any given time, each mouse can choose to eat a specific cheese wheel. However, mice are selective, and a single cheese wheel cannot be eaten by multiple mice at the same time. Nonetheless, a mouse can switch from one cheese wheel to another at any moment, even if the new wheel was previously being eaten by another mouse.
Mice dislike eating cheese after it starts to spoil, but they cannot leave any cheese uneaten. They aim to organize their cheese consumption to minimize the value t, which represents the number of hours a cheese wheel is still being eaten after it begins to spoil. Help the mice determine how to achieve this.
Input
The first line of the input contains two integers n and m (1 <= n, m <= 30). The next n lines each contain three integers: p_i, r_i, and d_i (1 <= p_i <= 10^5, 0 <= r_i < d_i <= 10^7). Following these are m lines, each containing one integer s_j (1 <= s_j <= 10^5).
Output
Output a single real number - the desired minimum t. The answer should be accurate to 10^{-4}.
Explanation of the example
In the first example, the mice should organize their cheese consumption as follows: Initially, the first mouse starts eating the first cheese wheel. When the second wheel becomes available, it switches to the second wheel (leaving 9 grams of the first wheel uneaten). Meanwhile, the second mouse begins eating the first cheese wheel. After 2.5 hours, the first mouse finishes the second wheel (0.5 hours after it starts to spoil) and returns to the first wheel (by this time, the second mouse has consumed another 5 grams, leaving 4 grams). Consequently, the first mouse finishes the first wheel in another hour, also 0.5 hours after it starts to spoil.
In the second example, the mouse manages to consume the cheese before it begins to spoil.