FX的补考

题目背景

这个故事告诉我们要多做题，少做梦。U695279 FX的补考（加强版）

题目描述

小樊因为每次写代码时都找“场外援助”，所以在一次模拟赛中，他因为抄别人的代码被抓了，在经过一番口头教育之后，老师让他补考。考试中总共有$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 5 1
10 20
3 3
1 1

输出样例 #1

30

输入样例 #2

2 5 1
10 20
3 3
1 2

输出样例 #2

20

说明/提示

样例解释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$为正。