Date Shopping

Techgig

August 06, 2022 by aAshish

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

Constraints

1<= B <=10^6

1<= J, T <=1000

1<= Ji, Ti =10^6

Output Format

Print the maximum money Varun can spend shopping.

Sample TestCase 1

Input

3 3

5 7 9

6 2 7

Output

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);
    }
}