题目描述

小核桃来到食堂，准备买一份午餐。

食堂有 $n$ 种主食和 $m$ 种菜品。第 $i$ 种主食的价格为 $a_i$ 元，第 $j$ 种菜品的价格为 $b_j$ 元。

小核桃要恰好选择一种主食和一种菜品，两者的总价不能超过 $p$ 元。

请问，小核桃一共有多少种不同的搭配方法？

只要选择的主食种类或菜品种类不同，就算不同的搭配。价格相同的不同种类，也要分别计算。

输入格式

从文件 lunch.in 中读取数据。

第一行包含三个整数 $n,m,p$，分别表示主食种类数、菜品种类数和小核桃的预算。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各主食的价格。

第三行包含 $m$ 个整数 $b_1,b_2,\ldots,b_m$，表示各菜品的价格。

输出格式

输出到文件 lunch.out 中。

输出一个整数，表示总价不超过 $p$ 元的搭配方法数。如果没有符合要求的搭配，输出 $0$。

3 2 10
2 4 7
3 6

5

2 3 6
3 3
3 3 4

4

样例解释

样例 #1 中，可以选择的主食与菜品价格分别为：$(2,3)$、$(2,6)$、$(4,3)$、$(4,6)$、$(7,3)$，共 $5$ 种搭配。

样例 #2 中，两种主食都可以分别搭配第一种或第二种菜品，共有 $2\times 2=4$ 种搭配。虽然它们的价格相同，但种类不同，要分别计算。

数据规模与约定

对于所有数据，保证：

• $1\le n,m\le 2000$；
• $1\le a_i,b_j\le 10^4$；
• $1\le p\le 2\times 10^4$。

本题采用子任务捆绑计分。只有通过某个子任务内的所有测试点，才能获得该子任务的分数。各子任务独立计分。

下发文件

下载三组测试数据，非真实测试数据