Tommy's passion for lemons led him to embark on a delightful venture – running a lemonade stand! Driven by his desire to create not just a refreshing beverage but also an economically savvy concoction, Tommy meticulously crafts a collection of
lemonade recipes. Each recipe is a carefully balanced blend of lemons, sugar, and mint, contributing to both the overall cost and flavour of the lemonade.
Tommy's curiosity has now turned to understanding the intricate relationship between the cost of ingredients and the flavour ratings of his lemonade recipes. The
recipe is characterized by three constants –
,
, and
– that influence how the flavour ratings evolve after adding
mL of water. Specifically, the flavour ratings can be calculated as
. Additionally, Tommy can add any amount of water he wants to each recipe, and he will incur a cost of one dollar for every millilitre of water added. Since Tommy is not a wizard, he cannot add a negative amount of water.
Given Tommy's financial constraints, he finds himself in a situation where he can only afford a lemonade stand capable of supporting him to produce lemonade with up to
recipes. Despite the financial challenges, Tommy is determined to ensure that his lemonade stand exudes diversity and uniqueness. Therefore, with careful consideration, he aims to select exactly
recipes that offer a varied and appealing range of flavours to attract a broad customer base.
Tommy, with a keen eye on maximizing his lemonade stand's profit, has defined profitability as the ratio of the sum of flavour ratings to the sum of costs. In his quest for the most sought-after lemonade stand in town, Tommy seeks your expertise to determine the maximum possible profitability. Your task is to assist Tommy in selecting a subset of size
from the
lemonade recipes that will result in the highest achievable profitability.
Input Specification
The first line of input contains two space-separated integers,
and
.
The following
lines of input each contain three space-separated integers,
,
, and
.
The following table shows how the available
marks are distributed.
Marks Awarded |  |  |  |  |  |
marks |  |  |  |  |  |
marks |  |  |  |  |  |
Output Specification
Output the highest achievable profitability of
selected recipes.
Your answer will be considered correct if it is within an absolute or relative error of
.
Sample Input
Copy
5 3
1 1 1
3 2 4
4 6 7
6 4 10
4 7 6
Sample Output
Copy
-2.662422376
Explanation for Sample
Tommy is dealing with five lemonade recipes, and he can afford to choose three recipes for his stand. The recipe
,
, and
have respective flavor rating of
,
, and
. The profitability is calculated by dividing the sum of flavour ratings by the sum of costs. After thorough evaluation, the highest achievable profitability is
which is approximately
, making this combination of recipes the most lucrative for Tommy's lemonade stand.
Comments