Tony works in Huron Designs, a website that receives requests for advertising design projects. Right now, Tony has $$$n$$$ open requests, where the deadline of the $$$i$$$-th request is $$$d_i$$$ seconds from now, the base profit of it is $$$p_i$$$, and the time to complete it is $$$c_i$$$ after Tony starts working on it. Tony can work on at most one request at the same time.
A feature of Huron Designs is that the clients can give an optional bonus to the designers to recognize their work. You, as the assistant of Tony, have analyzed the previous transactions of the clients, and you have estimated that the client of the $$$i$$$-th request would pay $$$x_i$$$ of bonus if Tony completes the $$$i$$$-th request on or before $$$y_i$$$ seconds from now. You don't know the exact value of $$$x_i$$$ and $$$y_i$$$, but you know that $$$x_i$$$ is a real number chosen uniformly at random from the range $$$[lx_i,rx_i]$$$ and $$$y_i$$$ is a real number chosen uniformly at random from the range $$$[ly_i,ry_i]$$$.
Your task is to find a subset of the requests that Tony should accept and the order in which the chosen requests should be completed to maximize the expected value of Tony's profit. Each one of the chosen requests should be completed on or before its respective deadline.
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 20$$$).
Each of the following $$$n$$$ lines contains seven integers $$$d_i, p_i, c_i, lx_i, rx_i, ly_i, ry_i$$$ ($$$1 \leq d_i, p_i, c_i \leq 10^9$$$, $$$0 \leq lx_i \leq rx_i \leq 10^9$$$ and $$$1 \leq ly_i \leq ry_i \leq 10^9$$$).
Print one number — the maximum expected value of Tony's profit.
Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.
Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.
25 10 5 2 2 1 415 20 5 3 3 10 15
33.000000000000
210 15 8 50 50 1 820 1 7 20 30 6 10
19.750000000000
| Название |
|---|


