408047: GYM102966 K Kitchen Waste

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Kitchen Wastetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

As some of you may know, Jaime, the delivery package company owner, is also owner of a famous restaurant at Quadradonia. Jaime's restaurant iconic plate is an exquisite clam chowder, which is served inside a sourdough bread that is used as a bowl. The clam chowder and the sourdough bread are homemade using zero waste cooking, which means literally, to have no waste left behind while cooking a meal. What is not zero waste is the way the kitchen staff serves the bowls.

For tonights service the restaurant staff expects to serve $$$N$$$ sourdough breads of the clam chowder pouring it from the $$$M$$$ dutch ovens where the clam chowder was prepared. To make their work easier, the kitchen staff have placed the $$$N$$$ breads in a line, in such way they always know what is the next bread to be filled with soup, since all bread is homemade, not all of them may hold the same amount of soup. Also, there will be only one person serving the soup from a dutch oven at the time, so all the content that can be used from a dutch oven is used before taking the next dutch oven to use for the soup service, similar to what was done with the bread, they placed the $$$M$$$ dutch ovens in a line, so that when the person serving the soup decides to change the dutch oven, they only have to take the next dutch oven in line.

When the service starts, the first dutch oven from the line of dutch ovens is prepared for serving, and the first clam chowder should be served into the first bread from the line of breads. Before serving the soup, the staff will check, if the dutch oven has enough soup to fill the bread, then, they serve it, otherwise they will take the next dutch oven of soup from the line of dutch ovens and send the current dutch oven to the dishwasher, throwing the clam chowder left on the dutch oven as discard. Once all the $$$N$$$ breads are served, the service is over, and, as clam chowder should be fresh every night, all the soup in the current dutch oven is discarded, and the same is done to all dutch ovens from the line that were not used. As you can see, this way of serving the chowder may tend to have a lot of waste.

Jaime wants to measure how wasteful this method is, so he came to you and hired you to measure the waste. Given the volume of soup each dutch oven in the line of dutch ovens holds, and the volume of soup each sourdough bread in the line of breads needs to be filled, find how much soup will be wasted during the soup serving service.

Input

The first line of input contains two integers separated by a space $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq M \leq 1000$$$), representing the number of sourdough breads to serve, and the number of dutch ovens in the line. The next line contains $$$N$$$ integer numbers separated by a space, where the $$$i$$$-th number represent the volume needed to fill the $$$i$$$-th bread in the line, this volume will be a number between $$$1$$$ and $$$20$$$. The next and last line contains $$$M$$$ integer numbers separated by a space, where the $$$i$$$-th number represents the volume of soup the $$$i$$$-th dutch oven has, this volume will be a number between $$$20$$$ and $$$100$$$. It is guaranteed all breads can be served with the given input.

Output

Output a line containing one integer number, the amount of waste Jaime's kitchen staff will waste in the service.

ExamplesInput
5 5
20 20 20 20 20
20 20 20 20 20
Output
0
Input
5 6
1 2 3 4 5
20 20 20 20 20 20
Output
105

加入题单

上一题 下一题 算法标签: