题目描述

恐龙星球有着与地球截然不同的时间体系，这里的一天固定为 $100000$ 小时（记为 $H = 100000$）。星球上生活着 $n$ 只霸王龙，编号从 $1$ 到 $n$。对于每只霸王龙，我们会明确给出其一天的三个连续且不重叠的时间段划分（以时长表示，分别记为 $t_1$、$t_2$、$t_3$，均为非负整数，且满足 $t_1 + t_2 + t_3 = H$），三个时间段依次对应捕猎、休息、活动三种行为。

每只霸王龙的三个时间段分别对应一个固定的兴奋值系数 $a$、$b$、$c$（系数非负），即：时长为 $t_1$ 的时间段对应兴奋值系数 $a$，时长为 $t_2$ 的时间段对应系数 $b$，时长为 $t_3$ 的时间段对应系数 $c$。在任意一个小时内，若该小时属于这只霸王龙的某个时间段，则它在该小时的兴奋值为对应时间段的系数。

记 $s[i]$ 表示第 $i$ 个小时（$1 \le i \le 100000$）$n$ 只霸王龙的兴奋值总和，请你计算 $\max(s[1], s[2], \dots, s[100000])$ 的结果，即全天所有小时中，$n$ 只霸王龙兴奋值总和的最大值。

输入格式

第一行输入一个整数 $n$，表示霸王龙的数量。

接下来 $n$ 行，每行输入六个非负整数 $t_1, t_2, t_3, a, b, c$，其中 $t_1, t_2, t_3$ 是该霸王龙三个时间段的时长（满足 $t_1 + t_2 + t_3 = 100000$），$a, b, c$ 分别是三个时间段对应的兴奋值系数。

输出格式

输出一个整数，表示全天所有小时中 $n$ 只霸王龙兴奋值总和的最大值。

样例

1
0 0 100000 1 2 3

3

2
30000 50000 20000 5 3 4
20000 40000 40000 2 7 1

12

3
40000 30000 30000 6 9 5
20000 50000 30000 7 4 9
50000 20000 30000 3 10 6

23

4
30000 40000 30000 10 5 8
25000 25000 50000 7 12 6
45000 35000 20000 9 4 11
15000 55000 30000 8 12 13

43

样例解释

样例 1：仅 $1$ 只霸王龙，时间段划分为 $t_1=0, t_2=0, t_3=100000$，对应系数 $a=1, b=2, c=3$。该霸王龙全天 $100000$ 小时的兴奋值均为 $3$，故每个小时的总和 $s[i]$ 均为 $3$，最大值为 $3$。

样例 2：当 $i=30000$ 时，第一只霸王龙处于第一个时间段，兴奋值为 $5$，第二只霸王龙处于第二个时间段，兴奋值为 $7$，两只霸王龙的兴奋值总和为 $12$，可以证明不存在其他时间让总和更大。

数据范围

• 对于 $40\%$ 的数据：$1 \le n \le 100$。
• 对于 $100\%$ 的数据：$1 \le n \le 100000$，$0 \le t_1, t_2, t_3 \le 100000$ 且 $t_1 + t_2 + t_3 = 100000$，$0 \le a, b, c \le 10^7$。