Hotel Order Assignment Profit Maximization

You run a hotel with n rooms and have received m orders. The i^th room has a maintenance cost \(c_i\) and a capacity \(p_i\) (i.e. maximum number of people it can accommodate). You are also given m orders; the i^th order is characterized by two parameters \(v_i\) and \(d_i\). Here, \(v_i\) is the rental income that order would generate and \(d_i\) is the number of people for that order.

You must decide which orders to accept such that each accepted order can be assigned to a distinct room whose capacity is at least the number of people in the order. When an order is assigned to a room, the cost incurred is the maintenance cost of that room. The profit from an assignment is the rental income minus the room's maintenance cost. Note that orders for which no room exists with adequate capacity or for which the net profit (\(v_i - c_j\)) is non‐positive should be left unassigned.

You are allowed to accept at most \(o\) orders. Compute the maximum total profit, defined as the total rental income collected from the accepted orders minus the total maintenance cost of the rooms assigned to these orders.

Note: An order can only be assigned to a room if \(d_i \le p_j\) and each room can be used for at most one order.

The problem can be modeled as a maximum weighted bipartite matching with an extra limit on the number of assignments. One effective solution is to build a flow network as follows:

• Create a source node and a sink node.
• For each order \(i\), add an edge from the source to the order node with capacity 1 and cost 0.
• For each room \(j\), add an edge from the room node to the sink with capacity 1 and cost 0.
• For every order \(i\) and room \(j\) such that \(d_i \le p_j\) and \(v_i - c_j > 0\) (i.e. the assignment is profitable or non-negative), add an edge from order \(i\) to room \(j\) with capacity 1 and cost \(c_j - v_i\) (note that a negative cost here represents profit).

Then, using a minimum cost maximum flow algorithm, we try to send flows (each representing one assignment) one by one up to \(o\) flows. We stop if the next augmentation does not yield a negative cost (i.e. positive profit). The maximum profit is \(- (\text{total cost})\) accumulated over these flows.

The input and output formats are detailed below.

inputFormat

The first line contains three integers \(n, m, o\) (the number of rooms, the number of orders, and the maximum number of orders that can be accepted), separated by spaces.

The next \(n\) lines each contain two integers \(c_i\) and \(p_i\) representing the maintenance cost and capacity of the \(i^th\) room.

The following \(m\) lines each contain two integers \(v_i\) and \(d_i\) representing the rental income and the number of people for the \(i^th\) order.

It is guaranteed that \(1 \le n, m, o \le 100\) (or similar small constraints) so that a min cost flow solution will run efficiently.

outputFormat

Output a single integer — the maximum profit achievable by accepting at most \(o\) orders under the given constraints.

sample

3 4 2
3 3
5 5
1 2
10 2
8 3
2 1
6 4

14