1657: 销售计划

某贸易公司准备销售某一货物，每日购进若干数量的这种货物，用车运到各子公司销出。若每天最多发车1趟送往各公司，该车运的最大货物量为K。该公司下属有N个子公司，他们销售数量与销售收入不成正比，第I个公司售出的货物为J件，可收入A[I，J]元。

对于给定每日货物的购入单价，及每个子公司的销售收入表A，现要求制订该公司D天内使得该公司的利润最大的销售计划，编程求最大的利润。

　　输入文件包含若干组测试数据，每组测试数据有N+2行：

第一行：N，K，D（N≤100,K≤100,D≤30）

第二行：D个不大于100的正整数，表示每日的购入单价

第三行到第N+2行为一个矩阵A_N*K,其中A[I，J]（I=1,2,…N，J=1，2，…，K）为第I个公司若售出的货物为J件时的收入(A[I,j]为不大于10000的正整数)

　　有若干行：为每组测试数据所求的最大利润（无解时，输出-32767）。

　　说明：若将问题规模缩小为：某公司要在2天内售出7件货物。

　　N，K，D = 2，4，2

　　2天的单价分别为：5，4

　　各子公司销售收入表如下：

　　  6   10   16   18

 a=

      4     9     11    19 

　　（其中A[2，3] = 11表示公司2若售出3件货物可得到的收入为11）

　　要使得2天内销售利润最大，应在第一天送3件货物给第1子公司（利润为1），第二天送3件给公司1，送1件给公司2（利润为4），共得最大利润为5。

2 4 2
5 4
6 10 16 18
4 9 11 19

5