Ramen Shop Seating

Ron runs a ramen shop.

He recently noticed that customers wait a long time at lunch because the shop runs out of seats. A customer who waits long is less satisfied, and some customers give up and leave. He decided to add seats, and he asked you to write a simulator of customer behavior so he can judge how many seats are enough.

Customers arrive in groups. Each group is described by four values.

• $T_i$: the time the group arrives at the shop
• $P_i$: the number of customers in the group
• $W_i$: how long the group can wait for seats
• $E_i$: how long the group spends eating

Group $i$ arrives at time $T_i$ with $P_i$ customers together. If $P_i$ successive empty seats are available at one counter at that time, the group sits down at once. Otherwise the group waits until such seats become free. If the group cannot sit down at a time that is within $W_i$ of its arrival (the endpoint counts) and strictly before the closing time, the group gives up waiting and leaves. Also, when an earlier group is waiting, a later group cannot take seats until every earlier group has either sat down or left.

The shop has counters numbered $1$ to $N$, and counter $i$ has $C_i$ seats in one row. A group prefers seats far away from other customers. Precisely, the group chooses seats by the criteria below. Let $S_L$ be the number of successive empty seats to the left of the group after it sits down, and $S_R$ the number to the right. If there is no other customer on the left side, $S_L$ counts as infinity, and if there is no other customer on the right side, $S_R$ counts as infinity.

1. Choose seats maximizing $\min(S_L, S_R)$.
2. If several choices remain, choose seats maximizing $\max(S_L, S_R)$.
3. If several choices still remain, choose the counter with the smallest number.
4. If several choices still remain, choose the leftmost seats.

When several groups finish eating and leave at the same time and some group is waiting, assign seats to the waiting group after all the finishing groups have left.

The satisfaction of one customer is defined as follows.

• A customer of a group that leaves without eating has satisfaction $-1$.
• Otherwise the satisfaction is $(W_i - t_i)/W_i$, where $t_i$ is the time group $i$ actually waited. This value is between $0$ and $1$ inclusive.

Compute the average satisfaction over all customers.

The input consists of multiple datasets. Each dataset has the following format.

N M T
C_1 C_2 ... C_N
T_1 P_1 W_1 E_1
T_2 P_2 W_2 E_2
...
T_M P_M W_M E_M

$N$ is the number of counters, $M$ is the number of groups, and $T$ is the closing time. The shop always opens at time $0$. Every input value is an integer.

$1 \le N \le 100$, $1 \le M \le 10000$, $1 \le T \le 10^9$, $1 \le C_i \le 100$, $0 \le T_1 < T_2 < \dots < T_M < T$, $1 \le P_i \le \max_j C_j$, $1 \le W_i \le 10^9$, and $1 \le E_i \le 10^9$.

A line holding three zeros ends the input. That line is not a dataset.

For each dataset, print the average satisfaction over all customers on one line. Round the value to $10$ digits after the decimal point and print exactly $10$ digits.