C - Project Selection Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は会社の新規事業担当として、 N 個のプロジェクト案の中から実行するものを選定しようとしています。各プロジェクトは実行するかしないかのどちらかであり、同じプロジェクトを複数回実行することはできません。また、プロジェクトを1つも選ばないことも許されます。

各プロジェクト i (1 \leq i \leq N) を実行するためには C_i 万円の費用が必要であり、実行すると P_i 万円の収益が得られます。ここで、収益と費用はそれぞれ独立した値であり、最大化の対象は収益の合計です。費用は予算の制約にのみ関わり、収益から差し引かれることはありません。

しかし、いくつかのプロジェクト同士は、担当チームや使用設備が競合するため、両方を同時に選ぶことができません。このような競合関係は M 組あり、 j 番目 (1 \leq j \leq M) の競合関係はプロジェクト U_j とプロジェクト V_j の両方を選ぶことができないことを表します。

高橋君に与えられた予算の上限は K 万円です。選んだプロジェクトの費用の合計が K 万円以下であり、かつどの競合関係についても両方のプロジェクトを同時に選ばないようにしたとき、選んだプロジェクトの収益の合計の最大値を求めてください。

すなわち、選んだプロジェクトの集合を S としたとき、以下の条件をすべて満たす範囲で \displaystyle\sum_{i \in S} P_i の最大値を求めてください。

  • \displaystyle\sum_{i \in S} C_i \leq K
  • すべての j (1 \leq j \leq M) について、 U_j と V_j が同時に S に含まれない（すなわち \{U_j, V_j\} \not\subseteq S）

プロジェクトを1つも選ばない場合（ S が空集合の場合）の収益の合計は 0 です。

制約

  • 1 \leq N \leq 18
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq K \leq 10^5
  • 1 \leq C_i \leq 10^5 (1 \leq i \leq N)
  • 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
  • 同じ競合関係が複数回与えられることはない
  • 入力はすべて整数

入力

N M K
C_1 P_1
C_2 P_2
\vdots
C_N P_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • 1 行目には、プロジェクトの数を表す整数 N 、競合関係の数を表す整数 M 、予算の上限を表す整数 K が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各プロジェクトの情報が与えられる。
  • 1 + i 行目 (1 \leq i \leq N) には、プロジェクト i を実行するために必要な費用 C_i と、得られる収益 P_i が、スペース区切りで与えられる。
  • N + 2 行目から N + M + 1 行目では、競合関係の情報が与えられる。 M = 0 の場合、この部分は存在しない。
  • N + 1 + j 行目 (1 \leq j \leq M) には、 j 番目の競合関係におけるプロジェクトの番号 U_j と V_j が、スペース区切りで与えられる。

出力

選んだプロジェクトの収益の合計の最大値を整数で 1 行に出力してください。

入力例 1

3 1 100
50 80
60 90
40 50
1 2

出力例 1

140

入力例 2

5 3 200
30 100
50 150
40 120
60 200
80 180
1 2
2 3
4 5

出力例 2

420

入力例 3

8 6 500
100 500
80 400
120 600
90 450
70 350
110 550
60 300
150 800
1 2
1 3
2 4
3 4
5 6
7 8

出力例 3

2350

Score : 366 pts

Problem Statement

Takahashi, as the person in charge of new business at his company, is trying to select which projects to execute from N project proposals. Each project is either executed or not, and the same project cannot be executed more than once. It is also allowed to select no projects at all.

Executing each project i (1 \leq i \leq N) requires a cost of C_i ten-thousand yen, and yields a profit of P_i ten-thousand yen. Here, profit and cost are independent values, and the objective is to maximize the total profit. Cost is only relevant to the budget constraint and is not subtracted from the profit.

However, some pairs of projects conflict with each other due to competing team assignments or shared equipment, and cannot both be selected at the same time. There are M such conflict relationships, and the j-th (1 \leq j \leq M) conflict relationship indicates that both project U_j and project V_j cannot be selected simultaneously.

Takahashi's budget limit is K ten-thousand yen. Find the maximum total profit of the selected projects such that the total cost of the selected projects is at most K ten-thousand yen and no conflict relationship has both projects selected simultaneously.

In other words, letting S be the set of selected projects, find the maximum value of \displaystyle\sum_{i \in S} P_i subject to all of the following conditions:

  • \displaystyle\sum_{i \in S} C_i \leq K
  • For all j (1 \leq j \leq M), U_j and V_j are not both contained in S (i.e., \{U_j, V_j\} \not\subseteq S)

If no projects are selected (i.e., S is the empty set), the total profit is 0.

Constraints

  • 1 \leq N \leq 18
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq K \leq 10^5
  • 1 \leq C_i \leq 10^5 (1 \leq i \leq N)
  • 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
  • The same conflict relationship is not given more than once
  • All inputs are integers

Input

N M K
C_1 P_1
C_2 P_2
\vdots
C_N P_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • The first line contains three space-separated integers: N representing the number of projects, M representing the number of conflict relationships, and K representing the budget limit.
  • From the 2nd line to the (N + 1)-th line, information about each project is given.
  • The (1 + i)-th line (1 \leq i \leq N) contains the cost C_i required to execute project i and the profit P_i obtained, separated by a space.
  • From the (N + 2)-th line to the (N + M + 1)-th line, information about the conflict relationships is given. If M = 0, this part does not exist.
  • The (N + 1 + j)-th line (1 \leq j \leq M) contains the project numbers U_j and V_j involved in the j-th conflict relationship, separated by a space.

Output

Output the maximum total profit of the selected projects as an integer on a single line.

Sample Input 1

3 1 100
50 80
60 90
40 50
1 2

Sample Output 1

140

Sample Input 2

5 3 200
30 100
50 150
40 120
60 200
80 180
1 2
2 3
4 5

Sample Output 2

420

Sample Input 3

8 6 500
100 500
80 400
120 600
90 450
70 350
110 550
60 300
150 800
1 2
1 3
2 4
3 4
5 6
7 8

Sample Output 3

2350