There are N students and two halls named Hall A and Hall B. Each hall can accommodate at most N/2 students.

You are given two arrays hallA and hallB of size N representing the time it takes for ith student to reach the respective halls. You have to organize the class by instructing each student to go to exactly one hall which can be either Hall A or Hall B.

Find the minimum sum of time taken to organize the class.

• First line contains N, number of students
• Next line contains array Hall A denoting time taken for the ith student to enter Hall A
• Next line contains array Hall B denoting time taken for the ith student to enter Hall B

Example:

N - 2
A - [12, 11]
B - [10, 7]
output: 19
# choose one student from A[0] and another from B[1]

N - 4
A - [8, 4, 2, 1]
B - [6, 4, 6, 1]
output: 13
# choose 4, 2 from A and 6, 1 from B

ANSWER THIS IN O(N)