prithivMLmods/Coder-Stat

1 2 3 4<h1>力持ち</h1>5 6<p>7力持ちたちが集う力持ち学園がありました。力持ち学園の運動会では、力持ちたちが隊列を組んで行進します。8</p>9<p>10力持ちたちは常に自分たちの力を誇示したい一方で、彼らの大半は自分で歩きたくありません。そこで彼らの一部が一番下になり、その上に大勢の人を縦一列に持ちあげて歩くことで、実際に歩く人数を減らそうと考えました。11</p>12 13<p>14はじめに、<var>N</var> 人の力持ちは地面の上に横一列に並んでいて、それぞれ左側から １,２,３,..., <var>N</var> と通し番号で呼ばれています。通し番号 <var>i</var> の力持ちの体重は <var>w<sub>i</sub></var> で最大 <var>c<sub>i</sub></var> の重量まで持つことができます。15</p>16<p>17力持ちは、以下の条件をすべて満たすときだけ、隣に立っている左右どちらかの力持ちを持ちあげることができます。18</p>19<ul>20<li> 自分の上下には力持ちはいない。つまり、誰かに持ち上げられてもいないし、誰かを持ちあげてもいない。</li>21<li> 隣の力持ちの体重が、自分が持つことのできる最大の重量以下である。ただし、隣の力持ちが既に誰かを持ち上げているなら、縦に積み上がった力持ちたちの体重の合計が、自分が持つことのできる最大の重量以下でなければならない。</li>22</ul>23 24<p>25例えば、次のような３人の力持ちの隊列を考えてみましょう。26</p>27 28<center>29<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_PCK2014_mightyMan1" width="240">30</center>31<br>32 33<p>34下図のように、２の力持ちが持つことのできる重さが <var>w<sub>3</sub></var> 以上のとき、２の力持ちは３の力持ちを持ちあげることができます。続いて、１の力持ちが持つことのできる重さが <var>w<sub>2</sub></var> + <var>w<sub>3</sub></var> 以上のとき、１の力持ちは２の力持ちを持ちあげることができます。35</p>36 37<center>38<table>39<tr>40<td><img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_PCK2014_mightyMan2"  width="240"></td>41<td>42&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;43&rarr;44&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;45</td>46<td><img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_PCK2014_mightyMan3"  width="240"></td>47</tr>48</table>49</center>50<br>51 52<p>53また、下図のように３の力持ちが２の力持ちを持ちあげた場合は、１の力持ちの隣が、２の力持ちを持った３の力持ちになるので、１の力持ちは３の力持ちを持ちあげることができます。 54</p>55 56<center>57<table>58<tr>59<td><img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_PCK2014_mightyMan4"  width="240"></td>60<td>61&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;62&rarr;63&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;64</td>65<td><img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_PCK2014_mightyMan5"  width="240"></td>66</tr>67</table>68</center>69 70<br>71 72<p>73２の力持ちが、下の図のように１と３の力持ちを両方持つことはできません。74</p>75 76<center>77<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_PCK2014_mightyMan6"  width="240">78</center>79<br>80 81<p>82力持ち学園の専属プログラマーとして、一番下で歩くことになる最小の人数を求めてください。83</p>84 85<h2>入力</h2>86<p>87入力は以下の形式で与えられる。 88</p>89 90<pre>91<var>N</var>92<var>c<sub>1</sub></var> <var>w<sub>1</sub></var>93<var>c<sub>2</sub></var> <var>w<sub>2</sub></var>94:95<var>c<sub>N</sub></var> <var>w<sub>N</sub></var>96</pre>97 98<p>991 行目に力持ちの人数 <var>N</var> (1 &le; <var>N</var> &le; 1000) が与えられる。続く <var>N</var> 行に <var>i</var> 番目の力持ちが持てる重量の最大値 <var>c<sub>i</sub></var> (1 &le; <var>c<sub>i</sub></var> &le; 100000) と体重 <var>w<sub>i</sub></var> (1 &le; <var>w<sub>i</sub></var> &le; 100000) が与えられる。100</p>101 102<h2>出力</h2>103<p>104最小の人数を１行に出力する。105</p>106 107<h2>入出力例 </h2>108<br>109 110<h2>入力例１ </h2>111<pre>1123113150 120114100 5011580 100116</pre>117 118<h2>出力例１</h2>119<pre>1201121</pre>122<br>123 124<h2>入力例２</h2>125<pre>126812750 10012820 2012930 2013090 50131140 3013230 6013359 12013410 10135</pre>136 137<h2>出力例２</h2>138<pre>1393 140</pre>141