Minimum Hours to Complete Assignments

You are given a set of assignments, where each assignment has a due date (in days) and requires a certain number of hours to complete. You can work on only one assignment at a time and must finish each assignment before or on its due date. The goal is to schedule the assignments in such a way that you finish all of them with no overlapping work periods while minimizing the total number of hours required.

An optimal strategy is to schedule the assignments backwards from their due dates using a greedy algorithm. In other words, for each assignment, you schedule it such that it ends exactly at its due date (or as late as possible without interfering with previously scheduled assignments), ensuring that there is no overlap between assignments.

The problem can be formulated mathematically as follows:

$$\text{Minimize}\quad \sum_{i=1}^{n} t_i$$

subject to the constraints that the time intervals allocated to complete each assignment are non-overlapping and each assignment is finished by its due date.

Here, \(t_i\) denotes the number of hours required to complete the \(i^{th}\) assignment.

inputFormat

The input consists of three lines:

1. The first line contains an integer (n), the number of assignments.
2. The second line contains (n) space-separated integers representing the due dates (in days) for each assignment.
3. The third line contains (n) space-separated integers representing the completion times (in hours) for each assignment.

outputFormat

Output a single integer representing the minimum total number of hours required to complete all assignments without overlapping.## sample

3
2 4 6
2 3 1

6