问题描述

卿爷和雯君正在安排一次市内旅游，旅游景点包括吴江路小吃街、南京路步行街、野生动物园、城隍庙、七宝街、福州路、新天地等若干经典去处。很快卿爷就发现，这些景点比较分散，从一个地方到另一个地方可能要花费比较长的时间，这样玩起来会很累。比如如果要你从野生动物园玩完后就去七宝街玩，你会立刻吟唱起草原上泥潭里一匹马的歌曲。为了让自己和心爱的人能够开开心心的游玩，卿爷决定规划一下游玩路线。

事实上，卿爷和雯君对每个游玩景点都有一个评价，表示对这个景点的喜好程度。这个景点的喜好程度和他俩到达这个景点的疲惫程度的差值将是他俩在这个景点游玩的满意程度。疲惫程度和到达这个景点的路程相关。卿爷希望，他俩对所有景点的满意程度之和能够最大。卿爷和雯君将从赤峰路校门口出发，不重复的游览全部景点。现在就请你来帮卿爷规划一下旅游线路吧！

输入格式

第 1 行，$N$、$M$、$D$ 三个正整数，表示有 $N$ 个景点，$M$ 条道路相连，每走 $D$ 单位的路程将给卿爷和雯君增加 1 单位的疲惫度。

第 2 行，$N$ 个正整数，表示卿爷和雯君对每个景点的喜好值。

第 3 行，$N$ 个正整数，表示从出发点到各个景点的距离。

第 4 到 $M + 3$ 行，每行 $A$、$B$、$C$ 三个正整数，表示景点 $A$ 和景点 $B$ 之间有一条长度为 $C$ 的互连道路。

$1 \leq N \leq 10$，$1 \leq C, D \leq 1000$，景点从 1 到 $N$ 编号。

输出格式

第一行，总的满意值，保留到小数点后两位。

第二行，最佳旅游线路，为景点编号，以空格隔开。如果有多解，输出字典序最小的方案。数据保证有解。

样例输入

5 5 1
5 3 3 8 10
1 1 1 1 1
1 2 8
2 3 2
2 4 1
1 5 2
3 5 3

样例输出

6.00
4 2 3 5 1