Algorithm for dividing items into buckets while minimizing total weight Let's say I have two buckets coloured red and blue, both of which can hold two rocks. I need to divide a set of $n$ weighted rocks into these buckets in such a way as to minimize the total weight of the rocks in the buckets, while filling each bucket to its capacity.

An additional constraint is this: the rocks are themselves coloured red or blue, and can only be placed in a bucket of the corresponding colour. Moreover, the rocks can be coloured multiple different colours. In this case, the rock can be placed in any of the buckets with which it shares a colour.

For example, if our rocks are

$$\begin{array}{c|c|c|} 
 &amp; \text{Colours} &amp; \text{Weight} \\ \hline
\text{Rock 1} &amp; \text{Red, blue} &amp; 1\\ \hline
\text{Rock 2} &amp; \text{Red} &amp; 2 \\ \hline
\text{Rock 3} &amp; \text{Red} &amp; 3 \\ \hline
\text{Rock 4} &amp; \text{Blue} &amp; 4 \\ \hline
\text{Rock 5} &amp; \text{Blue} &amp; 5 \\ \hline
\end{array}$$
then the optimal solution is
$$\begin{array}{c|c} 
\text{Red Bucket} &amp; \text{Blue Bucket} \\ \hline
\text{Rock 2} &amp; \text{Rock 1} \\ 
\text{Rock 3} &amp; \text{Rock 4}
\end{array}$$
as then the sum of the weights in the buckets is minimized.

One idea for an approximate algorithm as follows. First, sort the rocks in order of increasing weight. We make two passes of this list:


First pass: if the rock has only one colour, and if fewer than 2 rocks in the list so far have had that colour, then we can add that rock to the appropriate bucket. From the above example, we see that this step will place Rock 2 into the Red Bucket and Rock 4 into the Blue Bucket. (This step will never make an incorrect placement.)
Second pass (greedy): if the rock can fit into any of the buckets, put it there. 


This algorithm does not generate the optimal solution for the above example, since on the second pass it will incorrectly place Rock 1 into the Red Bucket.

My question is this: does there exist a polynomial time algorithm to solve this problem optimally for $k$ buckets and $n$ rocks? If not, are there any polynomial time algorithms that generate approximate solutions (better than the one I've given here)?
I assume that in the $k$ bucket case, each rock has up to $k$ colors (buckets) associated with it, which are the ones it can be put into. 

It seems to me that a polynomial time algorithm can be obtained by reduction to a minimum-cost flow problem, which can be solved in polynomial time. Create a network with $k + n + 1$ nodes: $n$ rock nodes, $k$ bucket nodes, and $1$ source node. The source node is adjacent to each of the rock nodes, with edge capacity 1 and edge cost equal to the weight of the rock. Each rock node is also adjacent to all the bucket nodes it can be put into, with edge capacity 1 and edge cost 0. The source node has a supply of $2k$ units, and each bucket node has a demand of 2 units. Any integer flow of value $2k$ corresponds to a feasible assignment of $2k$ rocks to the buckets. The minimum cost integer flow corresponds to an assignment of minimum weight.