软件安装
题目描述
mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:"Times New Roman"; color:black;background:white;mso-shading:windowtext;mso-pattern:solid white; mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">现在我们的手头有
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">N</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">个软件，对于一个软件</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">i</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">，它要占用</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">Wi</span><span lang="RU" style="font-size:
12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">的磁盘空间，它的价值为</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">Vi</span><span lang="RU" style="font-size:
12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">。我们希望从中选择一些软件安装到一台磁盘容量为</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">M</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">计算机上，使得这些软件的价值尽可能大（即</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">Vi</span><span lang="RU" style="font-size:
12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">的和最大）。</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">
</span><span lang="RU" style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">但是现在有个问题：软件之间存在依赖关系，即软件</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">i</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">只有在安装了软件</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">j</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">（包括软件</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">j</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">的直接或间接依赖）的情况下才能正确工作（软件</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">i</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">依赖软件</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">j)</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">0</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">。</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">
</span><span lang="RU" style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">我们现在知道了软件之间的依赖关系：软件</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">i</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">依赖软件</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">Di</span><span lang="RU" style="font-size:
12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">Di=0</span><span lang="RU" style="font-size:
12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">，这时只要这个软件安装了，它就能正常工作。</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">
</span></b>
输入格式
mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:"Times New Roman"; color:black;background:white;mso-shading:windowtext;mso-pattern:solid white; mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">第
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">1</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">行：</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">N, M</span><span lang="RU" style="font-size:12.0pt;
font-family:"Times New Roman";mso-fareast-font-family:宋体;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA"> </span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA"> </span><span style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:"Times New Roman";
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">（</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">0<=N<=100, 0<=M<=500</span><span style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:"Times New Roman";
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">）</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">
</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";
mso-fareast-font-family:宋体;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:ZH-CN;
mso-bidi-language:AR-SA"> </span><span lang="RU" style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:"Times New Roman";
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">第</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">2</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">行：</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">W1, W2, ... Wi, ..., Wn </span><span style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:ZH-CN;
mso-bidi-language:AR-SA">（</span><span lang="RU" style="font-size:12.0pt;
font-family:"Times New Roman";mso-fareast-font-family:"Times New Roman";
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">0<=Wi<=M</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
宋体;color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA"> </span><span style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:"Times New Roman";
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">）</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">
</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";
mso-fareast-font-family:宋体;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:ZH-CN;
mso-bidi-language:AR-SA"> </span><span lang="RU" style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:"Times New Roman";
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">第</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">3</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">行：</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">V1, V2, ..., Vi, ..., Vn </span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";
mso-fareast-font-family:宋体;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:ZH-CN;
mso-bidi-language:AR-SA"> </span><span style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:"Times New Roman";
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">（</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">0<=Vi<=1000</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
宋体;color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA"> </span><span style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:"Times New Roman";
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">）</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">
</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";
mso-fareast-font-family:宋体;color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:ZH-CN;
mso-bidi-language:AR-SA"> </span><span lang="RU" style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:"Times New Roman";
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">第</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">4</span><span lang="RU" style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">行：</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">D1, D2, ..., Di, ..., Dn</span><span lang="RU" style="font-size:12.0pt;font-family:
"Times New Roman";mso-fareast-font-family:宋体;color:black;background:white;
mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:
ZH-CN;mso-bidi-language:AR-SA"> </span></sub><span style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman";mso-bidi-font-family:"Times New Roman";color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language:
RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">（</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">0<=Di<=N, Di≠i</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
宋体;color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA"> </span><span style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman";mso-bidi-font-family:"Times New Roman";
color:black;background:white;mso-shading:windowtext;mso-pattern:solid white;
mso-ansi-language:RU;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA">）</span><span lang="RU" style="font-size:12.0pt;font-family:"Times New Roman";mso-fareast-font-family:
"Times New Roman";color:black;background:white;mso-shading:windowtext;
mso-pattern:solid white;mso-ansi-language:RU;mso-fareast-language:RU;
mso-bidi-language:AR-SA">
</span></b>
输出格式
<span lang="RU" style="font-size:12.0pt;font-family:宋体;mso-bidi-font-family:宋体;color:black;
background:white;mso-shading:windowtext;mso-pattern:solid white;mso-ansi-language: RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">一个整数，代表最大价值。</span>
3 10
5 5 6
2 3 4
0 1 1
5