prithivMLmods/Coder-Stat

1 2<H1><font color="#000000">Problem J:</font> ICPC: Ideal Coin Payment and Change</H1>3 4<p>5Taro, a boy who hates any inefficiencies, pays coins so that the number of coins to be returned as change is minimized in order to do smoothly when he buys something.6</p>7 8<p>9One day, however, he doubt if this way is really efficient.  When he pays more number of coins, a clerk consumes longer time to find the total value.  Maybe he should pay with least possible number of coins.10</p>11<p>12Thinking for a while, he has decided to take the middle course.  So he tries to minimize total number of paid coins and returned coins as change.13</p>14<p>15Now he is going to buy a product of P yen having several coins.  Since he is not good at calculation, please write a program that computes the minimal number of coins.16</p>17<p>18You may assume following things:19</p>20<ul>21<li>There are 6 kinds of coins, 1 yen, 5 yen, 10 yen, 50 yen, 100 yen and 500 yen.</li>22<li>The total value of coins he has is at least <i>P</i> yen.</li>23<li>A clerk will return the change with least number of coins.</li>24</ul>25 26 27<H2>Input</H2>28 29<p>30Input file contains several data sets.31One data set has following format:32</p>33<pre>34<i>P</i> <i>N</i><sub>1</sub> <i>N</i><sub>5</sub> <i>N</i><sub>10</sub> <i>N</i><sub>50</sub> <i>N</i><sub>100</sub> <i>N</i><sub>500</sub>35</pre>36<p>37<i>N<sub>i</sub></i> is an integer and is the number of coins of <i>i</i> yen that he have.38</p>39<p>40The end of input is denoted by a case where <i>P</i> = 0.  You should output nothing for this data set.41</p>42 43<H2>Output</H2>44 45<p>46Output total number of coins that are paid and are returned.47</p>48 49<H2>Constraints</H2>50<ul>51<li>Judge data contains at most 100 data sets.</li>52<li>0 &le; <i>N<sub>i</sub></i> &le; 1000  </li>53</ul>54 55<H2>Sample Input</H2>56<pre>57123 3 0 2 0 1 158999 9 9 9 9 9 9590 0 0 0 0 0 060</pre>61 62<H2>Output for the Sample Input</H2>63<pre>64665366</pre>67 68