G - Bear and Cavalry 2

3.9

13 votes
Sorting algorithm, Hard
Problem

Would you want to fight against bears riding horses? Me neither.

Limak is a grizzly bear. He is a general of the dreadful army of Bearland. The most important part of an army is the cavalry of course.

The cavalry of Bearland consists of N warriors and N horses, both numbered 1 through N. Limak knows the strength of each warrior W1, W2, ..., WN and the strength of each horse H1, H2, ..., HN.

A warrior together with his horse is called a unit. The strength of a unit is equal to the multiplied strengths of a warrior and a horse.

General Limak must assign all horses to warriors, one horse per warrior. The cavalry will consist of N units then.

The first warrior (the one with the strength W1) is called Bravebeart. He is always the first to charge the enemy. Limak decided that Bravebeart deserves some respect and his unit must be the strongest one, with no ties allowed. But is it possible?

Help Limak and check whether there is an assignment of horses to warriors for which the Bravebeart's unit is strictly stronger than any other unit. Print "YES" or "NO".

Input format

You are given multiple test cases.

The first line of input contains a single integer T, denoting the number of test cases.

For each test case the first line contains a single integer N.

The second line contains N integer numbers W1, W2, ..., WN, denoting the strengths of warriors. The first of the numbers is the strength of Bravebeart.

The third line contains N integers H1, H2, ..., HN, denoting the strengths of the horses.

Output format

For each test case find the answer and print it in a separate line.

Print "YES" (without the quotes) if there is an assignment where the strength of the Bravebeart's unit is strictly greater than the strength of any other unit. Otherwise, print "NO" (without the quotes).

Constraints

1 ≤ T ≤ 50
2 ≤ N ≤ 42
1 ≤ Wi, Hi ≤ 1000

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the first test case Bravebeart can take a horse of strength 6 to get the unit strength 12*6=72.

One of the ways to assign other horses to warriors is (9, 7), (7, 5), (1, 5), (20, 3), (10, 4). Indeed, the Bravebeart's unit is stronger than any other unit then.

In the second test case it's impossible to assign horses to warriors to satisfy the given condition.

Editor Image

?