3757：Simple Distributed storage system

Jack helps his mentor build a simple distributed storage system. He uses several servers and connects them as the following topology:

This distributed storage system contains a group of backend servers and a master server. The backend servers are different from each other while they store identical data, and all of them are invisible to client. When a client machine needs a file, it sends request to a master server. The master server collects different part of the file from some of backend servers. The strategy of the master is like follows.

Each backend server has its own processing throughput and transmission bandwidth. The master server knows that i^th backend server’s throughput is p_i (MB/s) and bandwidth is b_i (MB/s). As the result, omitted the propagation time, handling size of f_i MB data and sending to master machine needs time:

In addition, handling 1 MB data on ith server costs c_i. (Including electricity consumption and maintenance cost, etc.) In order to minimize the total cost, the master server should carefully decide which backends should be used and how much load they should process. At the same time, because of some consistency consideration, every time the master should choose exactly K backend servers to extract file, and each of them should take exactly the same time to finish the job.

Your task is to write a scheduling program for the master server. Assuming the size of the file is F MB, and the file can be infinitely divided.

The first line contains two integers N and K (K≤ N ≤ 20000), and a real number F. The master should choose exactly K machines among total N backend servers. The F is the size of the file.

The following N lines describe the details of each backend servers. Each line contains three real numbers, p_i, b_i and c_i, representing the processing throughput, bandwidth and unit cost.

The output file contains only one real number, the minimum cost. The answer is less than 10000000000 and should be rounded to four digits