Weighted Job Scheduling Problem Statement

You have 'N' jobs, each with a start time, end time, and profit. Your task is to identify the maximum profit that can be earned by scheduling these jobs such that no two jobs overlap.

Input:

The first line contains an integer 'T' denoting the number of test cases. 
For each test case: 
- The first line contains an integer 'N' denoting the number of jobs. 
- The second line contains 'N' space-separated integers representing the start times of the jobs. 
- The third line contains 'N' space-separated integers representing the end times of the jobs. 
- The fourth line contains 'N' space-separated integers representing the profits of the jobs. 

Output:

For each test case, output the maximum profit obtainable. Each result should be printed on a new line.

Example:

Input:

1 
4 
1 2 3 3 
3 5 4 5 
50 10 40 70

Output:

120

Constraints:

• 1 <= T <= 100
• 1 <= N <= 3000
• 1 <= Start[i] < End[i] <= 10^9
• 1 <= Profit[i] <= 10^9

Note:

The start time of one job can be equal to the end time of another.

Follow-up:

Can you devise an algorithm that solves this problem in O(N*log(N)) time complexity?