在智慧岛上，程序员小 Q 每天下班都会在 n 栋公寓之间兼职送外卖。这 n 栋公寓由 m 条双向道路连通，任意两栋公寓可通过这些道路相互到达。第 i 条道路连接公寓  u_i,v_i，长度为 w_i 米。
精通解梦的小 Q 早已在昨夜梦中知晓今日的所有订单信息：今晚，每栋公寓都恰好订了一份外卖，公寓 i 在 q_i 秒下单。小 Q 下班后会从 1 公寓骑上他的小电驴，从 0 秒开始送餐。小 Q 可以以不超过 1 m/s的速度沿道路移动，也可以在任意位置休息不动，到达公寓后的送餐时间可以忽略不计。当然，小 Q 不能在下单前将外卖送达，以免引起客户的恐慌。
对于一笔订单，小Q在订单发起后的不同时间送达将会产生不同收益。形式化地说，对一笔订单 j，外卖平台会规定 d 个送达时间节点 q_j<t₁<t₂<⋯<t_d（单位：秒），以及 d+1 个根据时间变化的收益p₁, p₂, ⋯, p_d+1。注意，收益不一定随着送达时间推迟而减少。设小 Q 在 T 秒送达外卖，那么他的收益为

聪明的你能告诉小 Q，今晚送完所有订单最多能挣多少钱吗？

第一行包含两个整数 n, m (1≤n≤14, n−1≤m≤(n(n−1))/2)，分别表示公寓的数量和道路的数量。
接下来 m 行，第 i 行包含三个整数  u_i,v_i,w_i (1≤u_i,v_i≤n, u_i≠v_i, 1≤w_i≤300)，表示第 i 条道路连接公寓 u_i,v_i，长度为 w_i 米。保证无重边。
接下来一行包含 n 个整数，第 i 个整数为 q_i (0≤q_i≤200)，表示第 i 栋公寓订单的发起时刻。
接下来 3n 行，每 3 行依次描述公寓  1,2,⋯,n  订单的收益信息。第一行包含一个整数  d (1≤d≤200)。第二行包含 d 个整数，第 i 个整数为  t_i (1≤t_i≤200)。第三行包含 d+1 个整数，第 d+1 个整数为  p_i (0≤p_i≤10⁸)。d,t_i,p_i的含义见题目描述。

输出一行一个整数，表示最大收益。

样例中，小 Q 在第 0 秒时已经在 1 号公寓等候订单；第 1 秒小 Q 完成 1 号订单（不计时间），获得 5 收益，随后动身前往 3 号公寓，并于第 3 秒抵达；第 3 秒小 Q 完成 3 号订单，获得 5 收益，随后动身前往 2 号公寓，并于第 4 秒抵达；第 4 秒小 Q 完成 2 号订单，获得 4 收益，此时全部订单完成，小 Q 获得最大收益 14。

 2020年河南省CCPC大学生程序设计竞赛