当前没有测试数据。

题目描述

一个人要送礼物给另外两个人，现有 𝑛n 件礼物要选一件送给第一个人，价值分别为 𝑎1,𝑎2,⋯ ,𝑎𝑛a1​,a2​,⋯,an​，有 𝑚m 件礼物要选一件送给第二个人，价值分别为 𝑏1,𝑏2,⋯ ,𝑏𝑚b1​,b2​,⋯,bm​。求在两件礼物之差不超过 𝑑d 的情况下，价值总和的最大值。

输入格式

𝑁N 𝑀M 𝐷D 𝐴1A1​ 𝐴2A2​ …… 𝐴𝑁AN​ 𝐵1B1​ 𝐵2B2​ …… 𝐵𝑀BM​

输出格式

高桥君选择礼物时必须满足条件，输出选择礼物时的价值之和，使其满足条件且价值之和最大。高桥不能满足条件选择时，输出- 1。

输入输出样例

输入数据 1

2 3 2
3 10
2 5 15

Copy

输出数据 1

8

Copy

输入数据 2

3 3 0
1 3 3
6 2 7

Copy

输出数据 2

-1

Copy

输入数据 3

1 1 1000000000000000000
1000000000000000000
1000000000000000000

Copy

输出数据 3

2000000000000000000

Copy

输入数据 4

8 6 1
2 5 6 5 2 1 7 9
7 2 5 5 2 4

Copy

输出数据 4

14