## Date Shopping

Varun has got a date after a long time and wants to look his best for his partner. He decides to go shopping to buy a new t-shirt and a pair of jeans but since it is the month’s end, he has a budget of only B rupees. He wants to spend the maximum money on jeans and t-shirt combo within the given budget. The problem is that he is good with his cloth choices but not with the calculations and asks for your help.

Varun has selected T t-shirts and J jeans. He provides you the prices of each of them and you have to determine the maximum money he can spend shopping. If it is not possible to buy the jeans and t-shirt with the given budget, you can tell him -1.

Example:1

Budget, B = 20

Jeans, Ji = [ 10, 5, 8 ]

T-shirts, Ti = [ 11, 7, 4 ]

The maximum money he can spend is 19 by buying the J3 jeans along with the T1 t-shirt.

Example:2

Budget, B = 10

Jeans, Ji = [ 8 , 9 , 10 ]

T-shirt, Ti = [ 4, 6, 3 ]

With the given budget, it is not possible for Varun to buy the jeans and t-shirt both. Thus, the maximum money he can spend is -1.

Can you help him shop and get ready for his date?

##### Input Format

The first line of input consists of the Budget, B

The second line of input consists of the number of jeans (J) and number of t-shirts (T) space-separately.

The third line of input consists of the J space-separated jeans prices, Ji

The fourth line of input consists of the T space-separated t-shirt prices, Ti

1<= B <=10^6

1<= J, T <=1000

1<= Ji, Ti =10^6

##### Output Format
Print the maximum money Varun can spend shopping.

Input
10
3 3
5 7 9
6 2 7
Output
9
###### Explanation

The maximum money can be spent by selecting J2 jeans and T2 t-shirt.

Maximum money  = 7 + 2 = 9

Java Solution
`import java.util.Scanner;class CandidateCode {    public static void main(String[] args) throws Exception {        Scanner sc = new Scanner(System.in);        int b = sc.nextInt();        int[] jeans = new int[sc.nextInt()];        int[] shirts = new int[sc.nextInt()];        for (int i = 0; i < jeans.length; i++) {            jeans[i] = sc.nextInt();        }        for (int i = 0; i < shirts.length; i++) {            shirts[i] = sc.nextInt();        }        int k = 0;        int mn = 0;        int pre = -1;        int flag = 0;        for (int j : jeans) {            for (int shirt : shirts) {                int s = j + shirt;                if (s <= b && flag == 0) {                    pre = s;                    flag = 1;                } else if (s <= b) {                    mn = s;                    if (mn > pre) {                        pre = mn;                    }                }                k = k + 1;            }        }        System.out.println(pre);    }}`

C# Solution

`using System;using System.IO;public class CandidateCode{    public static void Main(String[] args)    {        int b = (int)Convert.ToInt64(Console.ReadLine());        Console.ReadLine();        int[] jeans =  Array.ConvertAll(Console.ReadLine().Split(), int.Parse);        int[] shirts =  Array.ConvertAll(Console.ReadLine().Split(), int.Parse);        var k = 0;        var mn = 0;        var pre = -1;        var flag = 0;        foreach (int j in jeans)        {            foreach (int shirt in shirts)            {                var s = j + shirt;                if (s <= b && flag == 0)                {                    pre = s;                    flag = 1;                }                else if (s <= b)                {                    mn = s;                    if (mn > pre)                    {                        pre = mn;                    }                }                k = k + 1;            }        }        Console.WriteLine(pre);    }}`