3999. 制作人偶

【题目背景】

Asiram 是个可爱的男孩子, 他现在要买制作人偶的材料.

【题目描述】

他发现, 在可选的n 种材料之中, 两种材料之间的搭配, 有的会显得很漂亮, 而有的就显得不那么漂亮, 还有的不影响总体的美观程度.
为了量化两种材料之间的搭配的漂亮程度,Asiram 设置了一个“美观度”. 同时, 每种材料还有一定的价格,Asiram 并不是想用有限的金钱去实现尽量大的美观度, 而是希望他的每一分钱都能带来尽量大的美观度, 即,使美观度与花费的比值尽量大.

【输入格式】

输入第一行为两个整数n 和m
下面1 行, 有n 个整数, 第i 个数为材料i 的价格wi
再下面m 行, 每行三个整数a; b; v, 即材料a 与材料b 的搭配能带来v 的美观度

【输出格式】

一行一个浮点数, 表示美观度与价格的比值的最大值, 当你的输出与标答之间的相对误差小于10^ - 6 时即被判为正确.

【样例输入】

5 6
1 1 1 1 1
1 2 1
1 4 1
2 3 1
2 4 1
3 4 1
3 5 1

【样例输出】

1.25000000

【样例说明】

购买材料1,2,3,4 制作人偶是一种最优方案, 花费4 而能带来5 的美观度, 比值为1.25.

【大样例】

大输入样例 大输出样例

【数据规模与约定】

对于10% 的数据,n<=5,1<=m<=10
对于40% 的数据,n<=50,1<=m<=500
对于100% 的数据,n<=500,1<=m<=5000,0 < wi,vi<=100

【来源】

在此键入。