prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem A:</font> Cubist Artwork</H1>3 4<p>5<i>International Center for Picassonian Cubism</i> is a Spanish national museum of cubist artworks,6dedicated to Pablo Picasso. The center held a competition for an artwork that will be displayed7in front of the facade of the museum building. The artwork is a collection of cubes that are8piled up on the ground and is intended to amuse visitors, who will be curious how the shape of9the collection of cubes changes when it is seen from the front and the sides.10</p>11 12<p>13The artwork is a collection of cubes with edges of one foot long and is built on a flat ground14that is divided into a grid of one foot by one foot squares. Due to some technical reasons, cubes15of the artwork must be either put on the ground, fitting into a unit square in the grid, or put16on another cube in the way that the bottom face of the upper cube exactly meets the top face17of the lower cube. No other way of putting cubes is possible.18</p>19 20<p>21You are a member of the judging committee responsible for selecting one out of a plenty of22artwork proposals submitted to the competition. The decision is made primarily based on23artistic quality but the cost for installing the artwork is another important factor. Your task is24to investigate the installation cost for each proposal. The cost is proportional to the number of25cubes, so you have to figure out the minimum number of cubes needed for installation.26</p>27 28<p>29Each design proposal of an artwork consists of the front view and the side view (the view seen30from the right-hand side), as shown in Figure 1.31</p>32 33<center>34<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_cubistArtwork1"><br>35<p>Figure 1: An example of an artwork proposal</p>36</center>37 38<p>39The front view (resp., the side view) indicates the maximum heights of piles of cubes for each40column line (resp., row line) of the grid.41</p>42 43<p>44There are several ways to install this proposal of artwork, such as the following figures.45</p>46 47<center>48<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_cubistArtwork2"><br>49</center>50 51<p>52In these figures, the dotted lines on the ground indicate the grid lines. The left figure makes use53of 16 cubes, which is not optimal. That is, the artwork can be installed with a fewer number54of cubes. Actually, the right one is optimal and only uses 13 cubes. Note that, a single pile of55height three in the right figure plays the roles of two such piles in the left one.56</p>57 58<p>59Notice that swapping columns of cubes does not change the side view. Similarly, swapping60rows does not change the front view. Thus, such swaps do not change the costs of building the61artworks.62</p>63 64<p>65For example, consider the artwork proposal given in Figure 2.66</p>67 68<center>69<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_cubistArtwork3"><br>70<p>Figure 2: Another example of artwork proposal</p>71</center>72 73 74<p>75An optimal installation of this proposal of artwork can be achieved with 13 cubes, as shown76in the following figure, which can be obtained by exchanging the rightmost two columns of the77optimal installation of the artwork of Figure 1.78</p>79 80<center>81<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_cubistArtwork4"><br>82</center>83 84 85 86 87<H2>Input</H2>88 89<p>90The input is a sequence of datasets. The end of the input is indicated by a line containing two91zeros separated by a space. Each dataset is formatted as follows.92</p>93 94<p>95       <i>w d</i><br>96       <i>h</i><sub>1</sub> <i>h</i><sub>2</sub> ... <i>h<sub>w</sub></i><br>97       <i>h'</i><sub>1</sub> <i>h'</i><sub>2</sub> ... <i>h'<sub>d</sub></i><br>98</p>99 100<p>101The integers <i>w</i> and <i>d</i> separated by a space are the numbers of columns and rows of the grid,102respectively. You may assume 1 &le; <i>w</i> &le; 10 and 1 &le; <i>d</i> &le; 10. The integers separated by a space103in the second and third lines specify the shape of the artwork. The integers <i>h<sub>i</sub></i> (1 &le; <i>h<sub>i</sub></i> &le; 20,1041 &le; <i>i</i> &le; <i>w</i>) in the second line give the front view, i.e., the maximum heights of cubes per each105column line, ordered from left to right (seen from the front). The integers <i>h<sub>i</sub></i> (1 &le; <i>h<sub>i</sub></i> &le; 20,1061 &le; <i>i</i> &le; <i>d</i>) in the third line give the side view, i.e., the maximum heights of cubes per each row107line, ordered from left to right (seen from the right-hand side).108</p>109 110 111<H2>Output</H2>112 113<p>114For each dataset, output a line containing the minimum number of cubes. The output should115not contain any other extra characters.116</p>117 118<p>119You can assume that, for each dataset, there is at least one way to install the artwork.120</p>121 122<H2>Sample Input</H2>123<pre>1245 51251 2 3 4 51261 2 3 4 51275 51282 5 4 1 31294 1 5 3 21305 51311 2 3 4 51323 3 3 4 51333 31347 7 71357 7 71363 31374 4 41384 3 41394 31404 2 2 41414 2 11424 41432 8 8 81442 3 8 314510 101469 9 9 9 9 9 9 9 9 91479 9 9 9 9 9 9 9 9 914810 914920 1 20 20 20 20 20 18 20 2015020 20 20 20 7 20 20 20 201510 0152</pre>153 154<H2>Output for the Sample Input</H2>155<pre>1561515715158211592116015161131623216390164186165</pre>166