11566 - Let's Yum Cha!

Introduction

Yum cha 是粵語中的用來描述 "飲茶" 的術語，指吃不同的小點心，同時喝著中國茶的一種文化。飲茶是中國廣東與香港文化中的一部分，對廣東人來說，飲茶傳統上會在週末早上，全家人聚在一起聊天吃點心、喝喝中國茶，而茶是最重要的， 用來幫助消化食物。在過去，人們常去茶館飲茶，但是近幾年中，點心餐廳普及已經勝過茶館。

點 心在中文字面意思上 "點觸你的心"，點心可選擇的範圍相當廣泛，包括肉類、海鮮、甜品及水果的各種組合，點心通常藉由蒸的或者是油炸的烹飪方式，通常是用蒸籠或者是小盤子裝 著呈上來，而通常是三四件點心一盤，由於分量小，因此可以嘗試非常多樣的點心，最常見的點心有：'

·  Har gow: A delicate steamed dumpling with shrimp filling and thin (almost translucent) wheat starch skin. It is one of my favourite dim sum.

·  Siu mai: A small steamed dumpling with pork inside a thin wheat flour wrapper. It is usually topped off with crab roe and mushroom.

·  Char siu bau: A bun with Cantonese barbeque-flavoured pork and onions inside. It is probably the most famous dim sum around the world.

·  Sweet cream bun: A steamed bun with milk custard filling. It is sweet and spongy.

·  Spring roll: Consists of sliced carrot, wood-ear fungus, and sometimes meat, rolled inside a thin flour skin and deep-fried. It is crispy and delicious.
右圖即上述描述的點心，你能夠猜出是哪幾道嗎？

Description

今天有 N 位朋友一起飲茶，你和你的朋友將會付一樣的錢，而每個人(包括你) 最多付 $x，而餐廳有 K  種點心可以點，而對於一種點心，每個人將會獲得一個喜愛指數(favour index)，範圍介於 0 ~ 10 的整數。

現在將要點餐，你想要最大化自己的喜愛指數的總和，但是如果忽略朋友的喜愛點心，你將會被狠狠地痛打一頓，因此你改成要最大化平均每個人得到的喜愛指數，根據以下的公式

$$\frac{\text{Total favour value of all dishes ordered}}{N+1}$$

將這個公式計算出來的稱為 "mean favour value"，這並不表示每個人都會拿點心來吃，但是朋友總是會一起分享點心，來讓每個人都開心。

由於想要點多一點不同種的點心 ，你將不會點同一種點心大於 2 次，而且為了不浪費食物，也不會點大於 2(N+1) 盤點心，也就是每個人點 2 盤。帳單在計算時，不會只有點心的價錢，還會加上兩種基本費。 茶費: 每個人需要支付 $T 元的茶費。 10% 服務費: 在所有花費加總後，會再加收 10% 的服務費，採用無條件進位。

Input

輸入最多 25 組測資， 每組測資第一行會有四個整數 N, x, T, K，分別代表的如上描述

1 ≤ N ≤ 10, 1 ≤ x ≤ 100, 0 ≤ T ≤ 20, 1 ≤ K ≤ 100, $1 ≤ price of a dim sum ≤ $100. 

接著會有 K 行，每行表示點心的訊息，第一個整數表示點心的價錢，接著會有 N+1 個整數表示喜愛指數。

當  N = x = T = K = 0，結束程式。

Output

對於每組測資，輸出一行最大的 "mean favour value"，精準到小數點第二位。

Sample Input

3 10 5 2

6 7 5 6 9

10 9 10 10 8

0 0 0 0

Sample Output

16.00