NINJA7 - TWO SEQUENCES PROBLEM

no tags 

Given two lists A and B having the same length, find the length of longest subsequence of list A, whose sum is greater than or equal to the corresponding subsequence of list B. Corresponding subsequence means indices chosen in both of the lists must be the same.

Input format:

The first line contains an integer T, the number of test cases.

Then for each test cases, there are 3 lines.

The first line has an integer N, the number of elements in the lists A and B.

The second line contains N integers of the list A.

The third line contains N integers of the list B.

Output format:

For each test case, print the answer in a single line.

Constraints:

1 ≤ N ≤ 10^5

0 ≤ A[i] ≤ 10^7

0 ≤ B[i] ≤ 10^7

Sample

Input:
1
3
100 100 5
2 2 1000

Output:
2

hide comments
him0727: 2018-02-05 14:34:47

got so many WAs just because forgot to use long long...

Yogendra Kumar: 2016-02-27 08:27:19

Thanks to author, nice problem!

Last edit: 2016-02-27 08:29:44
Yogendra Kumar: 2016-02-27 08:22:05

@lazan_037, output 0 if there is not subsequence like that.

lazan_037: 2016-02-23 21:59:47

What if there is not subsequence like that?


Added by:mombassa
Date:2016-02-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY