prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem C:</font> Swimming Jam</H1>3 4<p>5Despite urging requests of the townspeople, the municipal office cannot afford to improve many6of the apparently deficient city amenities under this recession. The city swimming pool is one7of the typical examples. It has only two swimming lanes. The Municipal Fitness Agency, under8this circumstances, settled usage rules so that the limited facilities can be utilized fully.9</p>10<p>11Two lanes are to be used for one-way swimming of different directions. Swimmers are requested12to start swimming in one of the lanes, from its one end to the other, and then change the lane to13swim his/her way back. When he or she reaches the original starting end, he/she should return14to his/her initial lane and starts swimming again.15</p>16 17<p>18Each swimmer has his/her own natural constant pace. Swimmers, however, are not permitted19to pass other swimmers except at the ends of the pool; as the lanes are not wide enough, that20might cause accidents. If a swimmer is blocked by a slower swimmer, he/she has to follow the21slower swimmer at the slower pace until the end of the lane is reached. Note that the blocking22swimmer’s natural pace may be faster than the blocked swimmer; the blocking swimmer might23also be blocked by another swimmer ahead, whose natural pace is slower than the blocked24swimmer. Blocking would have taken place whether or not a faster swimmer was between them.25</p>26 27<p>28Swimmers can change their order if they reach the end of the lane simultaneously. They change29their order so that ones with faster natural pace swim in front. When a group of two or more30swimmers formed by a congestion reaches the end of the lane, they are considered to reach there31simultaneously, and thus change their order there.32</p>33 34<p>35The number of swimmers, their natural paces in times to swim from one end to the other, and36the numbers of laps they plan to swim are given. Note that here one "lap" means swimming37from one end to the other and then swimming back to the original end. Your task is to calculate38the time required for all the swimmers to finish their plans. All the swimmers start from the39same end of the pool at the same time, the faster swimmers in front.40</p>41 42<p>43In solving this problem, you can ignore the sizes of swimmers' bodies, and also ignore the time44required to change the lanes and the order in a group of swimmers at an end of the lanes.45</p>46 47<H2>Input</H2>48 49<p>50The input is a sequence of datasets. Each dataset is formatted as follows.51</p>52 53<p>54<i>n</i><br>55<i>t</i><sub>1</sub> <i>c</i><sub>1</sub><br>56...<br>57<i>t<sub>n</sub> c<sub>n</sub></i><br>58</p>59 60<p>61<i>n</i> is an integer (1 &le; <i>n</i> &le; 50) that represents the number of swimmers. <i>t<sub>i</sub></i> and <i>c<sub>i</sub></i> are integers62(1 &le; <i>t<sub>i</sub></i> &le; 300, 1 &le; <i>c<sub>i</sub></i> &le; 250) that represent the natural pace in times to swim from one end63to the other and the number of planned laps for the <i>i</i>-th swimmer, respectively. ti and ci are64separated by a space.65</p>66 67<p>68The end of the input is indicated by a line containing one zero.69</p>70 71 72<H2>Output</H2>73 74<p>75For each dataset, output the time required for all the swimmers to finish their plans in a line.76No extra characters should occur in the output.77 78</p>79 80<H2>Sample Input</H2>81<pre>8228310 308415 208528610 2408715 160883892 6907 2918 2924932 4947 2958 29618 197098</pre>99 100<H2>Output for the Sample Input</H2>101<pre>10260010348001043610540106</pre>107 108