该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

输入格式

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

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

输出格式

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

样例输入 1

1
0 0 100000 1 2 3

样例输出 1

3

样例输入 2

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

样例输出 2

12

样例输入 3

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

样例输出 3

23

样例输入 4

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

样例输出 4

43

数据范围与提示

对于40%的数据：

• 1 ≤ n ≤ 100

对于100%的数据：

• 1 ≤ n ≤ 100000

• 0 ≤ t₁、t₂、t₃ ≤ 100000，且 t₁ + t₂ + t₃ = 100000

• 0 ≤ a, b, c ≤ 10000000

样例解释

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

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