题目描述

塔子哥是一位优秀的化学家，他的研究领域是配制各种化学试剂。今天，他的研究重点是一种特殊的化学溶液。这种溶液需要通过合并其他的多种溶液来制备，以达到理想的浓度和体积。

在实验室里，塔子哥看到了 $n$ 种溶液，每一种都有无限多瓶，第 $i$ 种的溶液体积为 $x_i$ ，里面含有 $y_i$ 单位的该物质。他想要用这些溶液来制备出一个体积恰好为 $C$ 的溶液，且尽量浓，使得其中所含有的该物质数量尽可能多。

但是，这个过程并不容易。因为当两个瓶子的体积相等时，他们合并的过程中会发生化学反应，导致物质含量增加 $X$ 单位。这也就意味着，如果选择了某两种体积相等的溶液进行合并，可能会获得更高的物质含量。因此，为了制备出更浓的溶液，塔子哥需要仔细考虑每一步的操作。

最终，经过反复的试验和计算，塔子哥终于成功地制备出了体积恰好为 $C$ 的溶液，并且其中所含有的该物质数量也达到了最大值。他非常开心，因为他的努力得到了回报。现在，他想请你告诉他，这个溶液中所含有的该物质数量最多是多少。

输入描述

第一行三个正整数 $n$ ， $X$ ， $C$ ；

第二行 $n$ 个正整数 $x_1,x_2,...,x_n$ ，中间用空格隔开；

第三行 $n$ 个正整数 $y_1,y_2,...,y_n$ ，中间用空格隔开。

对于所有数据， $1\le n,X,C,y_i\le 1000$ ， $1\le x_i\le C$ 数据保证至少存在一种方案能够配制溶液体积恰好等于 $C$ 的溶液。

输出描述

输出一个整数，表示物质含量最多是多少。

样例

输入

3 4 16
5 3 4
2 4 1

输出

29