U689648 FX的补考

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

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

第一行三个整数$n$，$T$，$k$。 第二行$n$个整数$a_1$，$a_2$，$a_3$，$\dots$，$a_n$，表示每题的最高分数。 第三行$n$个整数$t_1$，$t_2$，$t_3$，$\dots$，$t_n$，表示拿到每题最高分所需的时间。 第四行$n$个整数$q_1$，$q_2$，$q_3$，$\dots$，$q_n$，表示每题属于的分组。

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

#### 样例解释1 两题在同一组，有时间减免，可以都做。 #### 样例解释2 两题不在同一组，只能做一道，选分数大的。 #### 数据规模与约定 $n\le21$，$T\le10^{18}$，$k\le10^9$，$1\le a_i\le10^9$，$1\le t_i\le10^9$，$q_i\le n$，$0\le q_i-q_{i-1}\le1$（在$i>1$时）,保证$k$为正。