title: Is it possible to sell all items with given costs to people with given amount of money
body: <p>Recently I ran into a real problem, which I can refolmulate as the following algorithmic task:</p>
  
  <p><b>Problem: </b><br/>Given a set of <code>N</code> persons, each having some amount of money, and a set of <code>M</code> items, each having some cost, is it possible to sell all of the items?</p>
  
  <p>Each item should be bought by at most one person, each person can buy multiple items so that their cost does not exceed the amount of money he has.</p>
  
  <p><b>My attempted solution:</b><br/>
  I was thinking in the direction of constructing a network and finding a maximal flow like this: <br/>
  - Make a bipartide graph with vertexes in one part corresponding to persons, and in other part - to items.<br/>
  - Connect persons to source <code>S</code> and set the edge capacities to money people have.<br/>
  - Connect items to sink <code>T</code> and set the edge capacities to the item costs. <br/>
  - Connect each person to the items he can buy and set edge capacities to the item costs</p>
  
  <p>In case each edge in the maximal flow found in this network is either empty or fully saturated, the problem will be solved by looking if all edges going to <code>T</code> are saturated, and if we want to know who should buy what item we would look at the edges between left and right parts.</p>
  
  <p>However but the problem is that the resulting flow can contain partially filled edges (meaning that a person partially paid for some item), and this case I am unable to eliminate.</p>