Problem Brief

Meeting Room

FULLTIMEOA

Given N groups of people who want to have a meeting in the only meeting room in the office. Each group has people[i] people, who want to start the meeting at the starting[i] time and end it at the ending[i] time (both inclusive).

No two groups can use the meeting room at the same time, If group j does not get the meeting room, then all the people[i] people cannot meet. Calculate the minimum number of people that cannot meet if the meeting room is optimally assigned to groups.

Note: Group i and j can get the meeting room one after the other if and only if end[i] < start[j].

Input Format:

• The first line contains N denoting the number of groups.
• The second line contains N space-separated integers denoting the number of people in each group
• The third line contains N space-separated integers denoting the starting time of each group's meeting
• The fourth line contains N space-separated integers denoting the ending time of each group's meeting

1Example 1

Input

people = [4, 3, 5, 6, 10], starting = [1, 2, 3, 6, 5], ending = [1, 2, 5, 7, 7]

Output

Explanation

The optimal assignment of the meeting room is as follows:

• Group 1 (4 people) uses the meeting room from time 1 to 1.
• Group 2 (3 people) uses the meeting room from time 2 to 2.
• Group 3 (5 people) cannot use the meeting room because it conflicts with Group 4.
• Group 4 (6 people) uses the meeting room from time 6 to 7.
• Group 5 (10 people) cannot use the meeting room because it conflicts with Group 4.

Therefore, the minimum number of people that cannot meet is 5 (Group 3) + 10 (Group 5) = 15.