U695279 FX的补考（加强版）

这个故事告诉我们要多做题，少做梦。[U689648 FX的补考](https://www.luogu.com.cn/problem/U689648)

小樊因为每次写代码时都找“场外援助”，所以在一次模拟赛中，他因为抄别人的代码被抓了，在经过一番口头教育之后，老师让他补考。考试中总共有$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 两题不在同一组，只能做一道，选分数大的。 #### 样例解释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$为正。