百度之星2009初赛第二轮题三------传输方案规划

问题背景

面对艰巨复杂的技术挑战，百度所崇尚的系统设计哲学是“简单可依赖”，而百度的工程师们正在互联网世界中实践着这种理念。这里正好有一个挑战，让作为百度之星的你小试牛刀：

在处理数以百亿计的网络信息的过程中，有一个很常见的问题：
怎么样将一个集群上的信息以最低的成本传输到另外一个集群上？

• 数据源集群A有n台服务器，编号为 1, 2, ..., n，i号服务器上待传输的数据量为A_i ，单位是GB。
• 目的地集群B有m台服务器，编号为 1, 2, ..., m，j号服务器上的空闲容量为 B_j，单位为 GB。
• A集群的i号服务器上的每GB数据对于B的集群的j号服务器收益为V_i,j，从 A 集群的 i 号服务器向 B 集群的 j 号服务器传输 1GB数据的开销为C_i,j。

你的任务是在保证A中的所有数据传输完毕的前提下，性价比V/C尽量高。其中V为所有数据在B集群上的价值之和，C为总开销。换句话说，若A集群的i号服务器向B集群的j号服务器发送了T_i,j个GB的数据，则性价比定义为：

输入格式

第1行两个整数n, m(1<=n,m<=50)，即集群A和B各自的服务器台数。
第2行包含n个不超过100的正整数A₁,A₂,…,A_n，即集群A中每台服务器的待传输数据量（单位：GB）。
第3行包含m个不超过100的正整数B₁,B₂,…,B_m，即集群B中每台服务器所能接受的最大数据量（单位：GB）。
第 4 ~ n+3 行每行包含m个不超过100的非负整数V_i,j，表示集群A的i号服务器中每GB数据对于集群B中的j号服务器的价值。
第 n+4 ~ 2n+3 行每行包含m个不超过100的正整数C_i,j，表示集群A的i号服务器中每GB数据传输到集群B中的j号服务器所需要的开销。

输出格式

仅一行，为最大性价比。输出保留三位小数（四舍五入）。如果A的数据无法传输完毕，输出-1。

样例输入

2 2
1 2
2 1
11 0
7 5
6 1
3 2

样例输出

2.091

样例解释

一个方案是：
集群A的1号服务器把所有数据传输到集群B的1号服务器，价值11，开销6。
集群A的2号服务器把1GB数据传输到集群B的1号服务器，价值7，开销3，然后把剩下的1GB数据传输到集群B的2号服务器，价值5，开销2。
性价比：(11+7+5)/(6+3+2)=2.091

另一个方案是：
集群A的1号服务器把所有数据传输到集群B的2号服务器，价值0，开销1。
集群A的2号服务器把所有数据传输到集群B的1号服务器，价值14，开销6。
性价比：(0+14)/(1+6)=2。

第一种方案更优。