题目内容

某电力公司管理$N$个变电站节点（编号$0$~$N$-$1$），节点间通过$M$条输电线路连接，相连节点属于同一供电区。定义供电区的不均衡度=区内最大负载与最小负载之差 ×节点数。请找出不均衡度最大的供电区，输出其不均衡度。若无有效供电区（节点数<$2$或$M$=$0$），输出-$1$。

输入描述

整型数组loads，长度为$N$，表示编号$0$~$N$-$1$的节点负载(MW); 二维整型数组edges，每行$2$个整数，表示该线路连接的两个节点编号，共$M$行。

约束:

$1$ ≤ $N$ ≤ $100$ $0$ ≤ $M$ ≤ $N$×($N$-$1$)/$2$ $0$ ≤ loads[i] ≤ $10000$ $0$ ≤ edges[j][0], edges[j][1] ≤ $N$-$1$ edges[j][0] ≠ edges[j][1]，无重复边

输出描述

整型，表示所有供电区中不均衡度的最大值。若无有效供电区，输出-$1$。

样例1

输入

[100,200,150,50,300],[[0,1],[1,2],[3,4]]

输出

500

说明

边($0$,$1$)($1$,$2$)将节点$0$,$1$,$2$连为供电区A，负载[$100$,$200$,$150$]，不均衡度=($200$-$100$)×$3$=$300$ 边($3$,$4$)将节点$3$,$4$连为供电区B，负载[$50$,$300$]，不均衡度=($300$-$50$)×$2$=$500$ 供电区B不均衡度更大，输出$500$

样例2

输入

[80,90,80,90],[[0,1],[1,2],[2,3]]

输出

40

说明

$4$个节点连为$1$个供电区，不均衡度=($90$-$80$)×$4$=$40$，输出$40$

样例3

输入

[100,200,300],[]

输出

-1

说明

每个节点独立，不构成有效供电区，输出-$1$