After finding a suitable residence in the Swiss Alps, Robin thought he finally had what it takes to be happy. But every day he woke up feeling that something was missing. Maybe it was the lack of English food in these parts? Spotting a market opportunity and solving his problem at the same time, he teamed up with the famous English chef Jim to open a restaurant nearby. While he has no doubts about Jim's talents as a chef, Robin wants to be sure that opening an English restaurant in the Swiss Alps is a good idea.
Fortunately, as a local, he knows the habits of restaurant customers. At the stroke of each hour, a group of people arrives of size that is uniformly random between and people (inclusive). The group finds the smallest completely unoccupied table that fits the group and occupies it. If they can not find such a table, the group leaves with great disappointment. Once seated, a group never leaves until the restaurant closes, as Jim has no difficulty keeping the guests entertained.
As an example, suppose the restaurant has tables of capacities , and . If groups of sizes and arrive (in that order), in the end there will be people in the restaurant. The first group occupies the table of capacity , the second group leaves and the last group occupies the table of capacity .
Robin plans to keep his restaurant open for hours in total. In the restaurant business the most important metric is the expected number of people in the restaurant when it closes. Can you help Robin calculate the expected occupancy after hours?
输入格式
The input consists of:
One line with three integers (, , ), the number of tables in the restaurant, the maximum group size, and the number of hours the restaurant is open.
One line with integers ( for each ) giving the capacities of the tables.
输出格式
Output the expected number of people in the restaurant when it closes. Your answer should have an absolute or relative error of at most .
