题目内容

某能源集团管理 $N$ 个区域（编号 $0$~$N-1$），每个区域有绿色能源减排量和化石能源碳排放量（单位均为吨）。区域间通过 $M$ 条输电线路连接，相连区域属于同一碳交易区。在同一碳交易区内，绿色减排量可跨区域抵消碳排放区，区内总减排量 $=$ $\max(0,\text{绿色减排量总量} - \text{化石能源碳排放量总量}) \times$ 区内区域数。请输出所有碳交易区中减排量的最大值。若无有效碳交易区（区域数 $<2$ 或 $M=0$），输出 $-1$。

输入描述

整数数组 green，长度为 $N$，表示编号 $0$~$N-1$ 的区域绿色能源减排量（吨）；

整数数组 carbon，长度为 $N$，表示编号 $0$~$N-1$ 的区域化石能源碳排放量（吨）；

二维整数数组 edges，每行 $2$ 个整数，表示该线路连接的两个区域编号，共 $M$ 行。

约束：

• $1 \leq N \leq 100$
• $0 \leq M \leq N \times (N-1)/2$
• $0 \leq \text{green}[i] \leq 10000$
• $0 \leq \text{carbon}[i] \leq 10000$
• $0 \leq \text{edges}[i][0], \text{edges}[i][1] \leq N-1$
• $\text{edges}[i][0] \neq \text{edges}[i][1]$，无重复边

输出描述

整数，表示所有碳交易区中减排量的最大值。若无有效碳交易区，输出 $-1$。

样例1

输入

[5,8,3,10],[4,2,6,9],[[0,1],[2,3]]

输出

14

说明

• 4 个区域，green = [5,8,3,10]，carbon = [4,2,6,9]
• 边 (0,1) 将区域 0,1 连为碳交易区 A：
  • 绿色减排总量 $=5+8=13$
  • 碳排放总量 $=4+2=6$
  • 减排量 $=(13-6)\times2=14$
• 边 (2,3) 将区域 2,3 连为碳交易区 B：
  • 绿色减排总量 $=3+10=13$
  • 碳排放总量 $=6+9=15$
  • 减排量 $=\max(0,13-15)\times2=0$
• 最大减排量为 $14$

样例2

输入

[3,5,7],[6,4,2],[[0,1],[1,2]]

输出

9

说明

• 3 个区域全连通为 1 个碳交易区：
  • 绿色减排总量 $=3+5+7=15$
  • 碳排放总量 $=6+4+2=12$
  • 减排量 $=(15-12)\times3=9$

样例3

输入

[2,4,6],[2,4,6],[]

输出

-1

说明

• 无有效碳交易区