题目描述

某地区有m座煤矿，其中第i号矿每年产量为a_i吨，现有火力发电厂一个，每年需用煤b吨，每年运行的固定费用（包括折旧费，不包括煤的运费）为h元，每吨原煤从第i号矿运到原有发电厂的运费为C_i0（i=1，2，…，m）。 <o:p></o:p>

<span lang="RU" style="mso-fareast-font-family:

宋体;mso-fareast-language:ZH-CN"> <o:p>   </o:p></span>

</p>

现规划新建一个发电厂，m座煤矿每年开采的原煤将全部供给这两座发电厂。现有n个备选的厂址。若在第j号备选厂址建新厂，每年运行的固定费用为h_j元。每吨原煤从第i号矿运到j号备选厂址的运费为C_ij（i=1，2，…，m；j=1，2，…，n）。 <o:p></o:p>

<span lang="RU" style="mso-fareast-font-family:

宋体;mso-fareast-language:ZH-CN"> <o:p>   </o:p></span>

</p>

试问：应把新厂厂址选取在何处？m座煤矿开采的原煤应如何分配给两个发电厂，才能使每年的总费用（发电厂运行费用与原煤运费之和）为最小。  <o:p></o:p>

输入格式

<p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;

text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:

normal">第1行：      m  b  h  n <o:p></o:p></b>

</p> <p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;

text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:

normal">第2行：      a₁  a₂ …  a_m </b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:

"Times New Roman";mso-fareast-language:ZH-CN">（</span>0<=a_i<=500, a₁+a₂+...+a_n>=b</b><span style="font-family:宋体;mso-ascii-font-family:

"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-fareast-language:

ZH-CN">）</span></b> <o:p></o:p>

</p> <p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;

text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:

normal">第3行：      h₁  h₂ …  h_n </b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:

"Times New Roman";mso-fareast-language:ZH-CN">（</span>0<=h_i<=100</b><span style="font-family:宋体;mso-ascii-font-family:

"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-fareast-language:

ZH-CN">）</span></b> <o:p></o:p>

</p> <p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;

text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:

normal">第4行：      C₁₀ C₂₀ … C_m0 </b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:

"Times New Roman";mso-fareast-language:ZH-CN">（</span>0<=Cij<=50</b><span style="font-family:宋体;mso-ascii-font-family:

"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-fareast-language:

ZH-CN">）</span> <o:p></o:p></b>

</p> <p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;

text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:

normal">第5行：      C₁₁ C₂₁ … C_m1 <o:p></o:p></b>

</p> <p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;

text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:

normal">                              …   … <o:p></o:p></b>

</p> <p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;

text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:

normal">第</b>n+4行：C_1n C_2n … C_mn <o:p></o:p>

</p>

输出格式

<p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;

text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:

normal">第1行：新厂址编号，如果有多个编号满足要求，输出最小的。 <o:p></o:p></b>

</p> <p class="MsoNormal" style="margin-left:12.0pt;mso-para-margin-left:1.0gd;

text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:

normal">第2行：总费用  <o:p></o:p></b>

</p>

4 2 7 9  3 1 10 3  6 3 7 1 10 2 7 4 9  1 2 4 3  6 6 8 2  4 10 8 4  10 2 9 2  7 6 6 2  9 3 7 1  2 1 6 9  3 1 10 9  4 2 1 8  2 1 3 4

8  49

数据范围与约定

<p class="MsoNormal" style="margin-left:24.0pt;mso-para-margin-left:2.0gd;<br />

text-align:justify;text-justify:inter-ideograph"><b style="mso-bidi-font-weight:

normal">对于所有数据, n<=50, m<=50000, b<=10000  <o:p></o:p></b>

</p>