AIOC Banner

Problem: Cats III: Off With Their Heads

Want to try solving this problem? You can submit your code online if you log in or register.

Cats III: Off With Their Heads

Input File:
Output File: cats.out
Time Limit: 1 second
Memory Limit: 64 MB

You really don't like cats. Unfortunately this fact has escaped your aunt, who has just given you the present of a lifetime: Cats in a Box.

Cats in a Box is a fiendish feline puzzle with two different types of pieces: heads and tails. There are n different heads and n different tails, which come in an assortment of loveable sizes and colours. Any head and tail can be combined to create a unique cat (so there are n2 different cats that you can make). The size of the resulting cat is the size of the head plus the size of the tail.

The box advertises that you can create "thousands of HUGE creations!" As you don't trust cat-lovers in the slightest, you are rather suspicious of their claims. You set out to determine precisely how large these creations are. Specifically, given the sizes of each of the head and tail pieces, your task is to calculate the size of the kth largest cat that can be created.


The first line of the input will contain the single integer n (1 <= n <= 100,000), the number of heads and the number of tails in the box. The second line of the input will contain the single integer k (1 <= k <= n2 and k <= 1,000,000,000), the number of possible "huge" creations that are advertised.

Following this will be n additional lines containing the integers a1, a2, ..., an, written one per line, where ai is the size of the ith head (1 <= ai <= 1,000,000). This will be followed by another n lines containing the integers b1, b2, ..., bn, also one per line, where bi is the size of the ith tail (1 <= bi <= 1,000,000). The heads and tails will be given in descending order, so that a1 >= a2 >= ... >= an and b1 >= b2 >= ... >= bn.


The output should consist of a single integer s, the size of the kth largest cat that can be created.

Sample Input


Sample Output



In the sample data above we have heads of sizes 8, 7, 7 and 3, and tails of sizes 9, 7, 4 and 2. You are asked to find the size of the seventh largest cat. The largest cats that can be created are:

Head #1:    8 #2:    7 #3:    7 #1:    8 #2:    7 #3:    7 #1:    8  ... 
Tail #1:    9 #1:    9 #1:    9 #2:    7 #2:    7 #2:    7 #3:    4  ... 
Cat size 17 16 16 15 14 14 12  ... 

The seventh largest cat therefore has size 12.


The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.


Privacy statement
© Australian Mathematics Trust 2001-2023

Page generated: 21 September 2023, 10:16pm AEST