D - Selection of Research Topic Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は大学の研究室に所属しており、今学期取り組む研究テーマを選ぼうとしています。研究室には N 個の研究テーマの候補があり、各テーマには 1 から N までの番号が付けられています。研究テーマ i に取り組むには、実験機材や資料の準備として C_i の費用がかかり、取り組んだ際に得られる学術的成果の価値は P_i と見積もられています。

研究テーマの間には M 個の前提関係が存在します。j 番目の前提関係は組 (U_j, V_j) で表され、研究テーマ U_j に取り組むならば研究テーマ V_j にも取り組まなければならないという制約を意味します（逆は必ずしも成り立ちません）。なお、前提関係は循環を含む場合があります。例えば、研究テーマ A が B を前提とし、B が A を前提とするような状況もあり得ます。この場合、A と B はどちらか一方だけを選ぶことはできず、両方選ぶか両方選ばないかのいずれかになります。

高橋君は、取り組む研究テーマの集合 S（S \subseteq \{1, 2, \ldots, N\}）を選びます。S は前提関係をすべて満たしている必要があります。すなわち、すべての j = 1, 2, \ldots, M について、研究テーマ U_j が S に含まれるならば研究テーマ V_j も S に含まれていなければなりません。S は空集合でも構いません。

高橋君の目標は、選んだ研究テーマから得られる成果の価値の合計から費用の合計を引いた値、すなわち

\sum_{i \in S} (P_i - C_i)

を最大化することです。S が空集合の場合、この値は 0 とします。

この最大値を求めてください。

制約

  • 1 \leq N \leq 15
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq P_i \leq 1000 （1 \leq i \leq N）
  • 1 \leq C_i \leq 1000 （1 \leq i \leq N）
  • 1 \leq U_j, V_j \leq N （1 \leq j \leq M）
  • U_j \neq V_j （1 \leq j \leq M）
  • 前提関係に重複はない。すなわち、(U_j, V_j) の組はすべて異なる。ただし、ある j, k について (U_j, V_j) = (V_k, U_k) となること（すなわち逆向きの関係が同時に存在すること）はあり得る。
  • 前提関係は循環を含みうる。すなわち、前提関係によって定まる有向グラフが非巡回であるとは限らない。
  • 入力はすべて整数である。

入力

N M
P_1 C_1
P_2 C_2
\vdots
P_N C_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • 1 行目には、研究テーマの数 N と前提関係の数 M が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目（1 \leq i \leq N）には、研究テーマ i の成果の価値 P_i と費用 C_i がスペース区切りで与えられる。
  • 続く M 行のうち j 行目（1 \leq j \leq M）には、j 番目の前提関係を表す U_j と V_j がスペース区切りで与えられる。これは研究テーマ U_j に取り組むならば研究テーマ V_j にも取り組まなければならないことを意味する。

出力

前提関係をすべて満たす研究テーマの集合 S を選んだときの、\sum_{i \in S} (P_i - C_i) の最大値を 1 行で出力せよ。

入力例 1

3 1
10 3
5 8
8 2
1 2

出力例 1

10

入力例 2

2 1
1 5
2 6
1 2

出力例 2

0

入力例 3

6 5
20 13
15 19
18 14
10 13
25 10
8 20
1 2
2 1
3 4
5 6
6 5

出力例 3

7

入力例 4

10 12
50 30
40 45
30 10
25 40
60 20
35 50
20 15
45 25
10 30
55 35
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7
10 1
4 7
8 10

出力例 4

70

入力例 5

1 0
5 3

出力例 5

2

Score : 400 pts

Problem Statement

Takahashi belongs to a university research lab and is trying to choose research topics to work on this semester. The lab has N candidate research topics, each numbered from 1 to N. Working on research topic i requires a cost of C_i for preparing experimental equipment and materials, and the value of academic results obtained from working on it is estimated to be P_i.

There are M prerequisite relationships among the research topics. The j-th prerequisite relationship is represented by the pair (U_j, V_j), meaning that if you work on research topic U_j, you must also work on research topic V_j (the converse does not necessarily hold). Note that prerequisite relationships may contain cycles. For example, a situation where research topic A requires B as a prerequisite and B requires A as a prerequisite is possible. In this case, you cannot choose only one of A and B; you must either choose both or choose neither.

Takahashi selects a set S (S \subseteq \{1, 2, \ldots, N\}) of research topics to work on. S must satisfy all prerequisite relationships. That is, for all j = 1, 2, \ldots, M, if research topic U_j is included in S, then research topic V_j must also be included in S. S may be the empty set.

Takahashi's goal is to maximize the total value of results obtained from the chosen research topics minus the total cost, namely

\sum_{i \in S} (P_i - C_i)

If S is the empty set, this value is 0.

Find this maximum value.

Constraints

  • 1 \leq N \leq 15
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq P_i \leq 1000 (1 \leq i \leq N)
  • 1 \leq C_i \leq 1000 (1 \leq i \leq N)
  • 1 \leq U_j, V_j \leq N (1 \leq j \leq M)
  • U_j \neq V_j (1 \leq j \leq M)
  • There are no duplicate prerequisite relationships. That is, all pairs (U_j, V_j) are distinct. However, it is possible that (U_j, V_j) = (V_k, U_k) for some j, k (i.e., reverse relationships may coexist).
  • Prerequisite relationships may contain cycles. That is, the directed graph defined by the prerequisite relationships is not necessarily acyclic.
  • All inputs are integers.

Input

N M
P_1 C_1
P_2 C_2
\vdots
P_N C_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • The first line contains the number of research topics N and the number of prerequisite relationships M, separated by a space.
  • In the following N lines, the i-th line (1 \leq i \leq N) contains the result value P_i and cost C_i of research topic i, separated by a space.
  • In the following M lines, the j-th line (1 \leq j \leq M) contains U_j and V_j representing the j-th prerequisite relationship, separated by a space. This means that if you work on research topic U_j, you must also work on research topic V_j.

Output

Output in a single line the maximum value of \sum_{i \in S} (P_i - C_i) when choosing a set S of research topics that satisfies all prerequisite relationships.

Sample Input 1

3 1
10 3
5 8
8 2
1 2

Sample Output 1

10

Sample Input 2

2 1
1 5
2 6
1 2

Sample Output 2

0

Sample Input 3

6 5
20 13
15 19
18 14
10 13
25 10
8 20
1 2
2 1
3 4
5 6
6 5

Sample Output 3

7

Sample Input 4

10 12
50 30
40 45
30 10
25 40
60 20
35 50
20 15
45 25
10 30
55 35
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7
10 1
4 7
8 10

Sample Output 4

70

Sample Input 5

1 0
5 3

Sample Output 5

2