9437: Career Path

Little Q has $X$ years of work experience and is currently unemployed. He wants to plan the career path for the next $N$ years and then retire. More specifically assume that today is the first day of the $1$\-st year and Little Q will officially retire on the last day of the $N$\-th year. There are $M$ companies in total the $i$\-th of which will be founded on the first day in the $L_i$\-th year and go bankrupt after paying all the employees' payment on the last day of the $R_i$\-th year. That is Little Q can start working for the company on the first day from the $L_i$\-th year to the $R_i$\-th year. Each company's fiscal year is from the first day to the last day of one year. An employee who starts on the first day and is still employed on the last day in one year will receive all the payments as a reward for working hard for a full year. Since Little Q is highly skilled every company is willing to hire him at any time. However Little Q only works for at most one company in a year and considers changing jobs after receiving all the payments on the last day of the year and being able to start at a different company on the first day of the next year. If he chooses to work for a company in a year he will gain a year of work experience. Assume that on the first day of some year Little Q has $Y$ years of work experience in total and has already worked for $Z$ full years continuously since the latest time being newly employed by the $i$\-th company and he will work for the $i$\-th company in this full year: - He will receive a payment of $A_i \times Y + B_i$ as a signing fee on the last day of this year if he is just newly employed i.e. $Z = 0$. - He will receive a payment of $C_i \times Y + D_i$ as annual cash salary on the last day of the year. If the company goes bankrupt just on the last day of the year he will also receive another cash payment of $\frac{(Z+2)(C_i \times Y + D_i)}{12}$ as compensation and then resign from the company. - He will receive a payment of $E_i \times Z + F_i$ as annual bonus on the last day of the year if the company doesn't go bankrupt on this day. - He will receive $G_i \times Y + H_i$ units of unvested stock shares as annual stock bonus on the last day of the year. The stock shares will be vested in equal portions upon Little Q along with the payments in each of the following $I_i$ years after the year receiving. Resigning from the company will automatically give up all the unvested stock shares and sell all vested shares forcedly. The stock price for the $i$\-th company in the $j$\-th year is $P_{ij}$ per share that is sell $p$ shares of stock of the $i$\-th company in the $j$\-th year will receive a payment of $P_{ij} \times p$ where $p$ could be any positive real number. The price is updated on the first day of every year and remains valid for the entire year. The stock price is $0$ if the company has not yet been founded or has already gone bankrupt. The only way to gain stock shares is from annual stock bonus but he can choose to sell vested stock shares at any time at the current price as long as he is still working at this company. Little Q must sell all the remaining vested stock shares at that year's price when he resigns from the company. Additionally the $i$\-th company has non-compete restrictions which means Little Q cannot work at the companies indexed in range $[U_i V_i]$ in the next year if he resigns from the $i$\-th company before the day he retires or the day the company goes bankrupt: - If there are surviving companies indexed in range $[U_i V_i]$ but Little Q chooses to take a gap year in the next year he will receive a one-time payment of $J_i \times W + K_i$ for the non-compete compensation since he has already worked for the company for $W$ full years continuously since the latest time being newly employed by the $i$\-th company. The gap year will not be counted in the number of years of work experience. - Otherwise he receives no non-compete compensation and cannot work in companies indexed in range within $[U_i V_i]$ in the next year. You need to help Little Q design a career path that maximizes his total income for the next $N$ years. The unsold stock shares will not be counted in Little Q's income.

The first line contains three integers $X$ $N$ and $M$. Then $2M$ lines follow where each of the $M$ companies is described by two lines. For the $i$\-th company: The first line consists of $15$ integers: $A_i$ $B_i$ $C_i$ $D_i$ $E_i$ $F_i$ $G_i$ $H_i$ $I_i$ $U_i$ $V_i$ $J_i$ $K_i$ $L_i$ and $R_i$. It is guaranteed that $I_i > 0$ $1 \le U_i \le V_i \le M$ and $0 \le L_i \le R_i \le N$. The second line consists of $N$ integers $P_{i1} P_{i2} \ldots P_{iN}$ representing the stock prices for the following $N$ years. It is guaranteed that the stock price is $0$ if the company has not yet been founded or has already gone bankrupt. This line would be empty if $N=0$. The stock option prices are integers in the range $[0 8000]$ and all other input values are integers in the range $[0 100]$.

Output a line containing a single real number indicating the maximum total income for the next $N$ years. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$. Formally speaking suppose that your output is $a$ and the jury's answer is $b$ your output is accepted if and only if $\frac{|a - b|}{\max(1 |b|)} \le 10^{-6}$.

#### 样例2 ##### 输入 ``` 5 10 2 3 1 2 48 1 6 2 8 4 2 2 1 24 1 6 1 1 2 2 3 3 0 0 0 0 1 5 5 25 0 10 3 10 5 1 1 2 10 3 10 0 0 0 1 3 1 3 1 3 1 ``` ##### 输出 ``` 1247.500000000000 ``` #### 样例3 ##### 输入 ``` 5 0 2 3 1 2 48 1 6 2 8 4 2 2 1 24 0 0 1 5 5 25 0 10 3 10 5 1 1 2 10 0 0 ``` ##### 输出 ``` 0.000000000000 ```