FX的补考（加强版）

题目背景

这个故事告诉我们要多做题，少做梦。U689648 FX的补考

题目描述

小樊因为每次写代码时都找“场外援助”，所以在一次模拟赛中，他因为抄别人的代码被抓了，在经过一番口头教育之后，老师让他补考。考试中总共有$n$道题目，总时间为$T$，对于第$i$题，小樊有一个能拿到的最高得分$a_i$，以及拿到这道题最高分数所需的初始时间$t_i$和最低时间$low_i$（他总是会拿到最高分后再做下一题）。并且小樊将这些题目分成了$m$组，第$i$题属于在组$q_i$中，同一组题目算法相似，因此对于第$j$组，小樊每做出其中的一道题，剩下的题目所需时间全部减去一个数$k_j$（第$i$道题的时间最小不小于$low_i$，每组做题顺序随意），小樊想知道，在比赛结束前，他最多可以拿到多少分。

输入格式

第一行三个整数$n$，$m$，$T$。
接下来四行各$n$个整数$a_i$，$t_i$，$q_i$，$low_i$，分别表示每题的最高分数，拿到每题最高分所需的初始时间，每题属于的分组，每题的最低时间。
第六行$m$个整数$k_j$，表示每组每次减少的时间。

输出格式

一行，一个整数，表示小樊可以拿到的最高分数。

输入输出样例

输入样例 #1

2 1 5
10 20
3 3
1 1
1 1
1

输出样例 #1

30

输入样例 #2

2 2 5
10 20
3 3
1 2
1 1
1 1

输出样例 #2

20

输入样例 #3

2 1 13
100 200
12 7
1 1
2 2
6

输出样例 #3

300

说明/提示

样例解释1

两题在同一组，有时间减免，可以都做。

样例解释2

两题不在同一组，只能做一道，选分数大的。

样例解释3

先做第一题，后做第二题，第二题受下限约束，总时间为$14$，只能做一道。
先做第二题，后做第一题，减免后总时间为$13$，可以都做。

数据规模与约定

$n$，$m\le24$，$T\le10^{18}$，$1\le a_i\le10^9$，$1\le t_i\le10^9$，$q_i\le n$，$1\le low_i\le 10^6$，$k_j\le10^9$，$0\le q_i-q_{i-1}\le1$（在$i>1$时），不保证$k_j$为正。