You are given n events where each takes one unit of time. Event i will provide a profit of gi dollars (gi 0) if started at or before time ti, where ti is an arbitrary real number.
(Note: If an event is not started by ti then there is no benefit in scheduling it at all.
All events can start as early as time 0.)

Given the most efficient algorithm you can to find a schedule that maximizes the profits.

Example:

Sample Input : V1 v2 v3 v4 v5 v6 v7 v8

Events ti: 0.1 1.3 2.1 2.2 4.4 4.5 5.1 5.2

Events gi 5 6 6 3 5

Question

You are given n events where each takes one unit of time. Event i will provide a profit of gi dollars (gi > 0) if started at or before time ti, where ti is an arbitrary real number.
(Note: If an event is not started by ti then there is no benefit in scheduling it at all.
All events can start as early as time 0.)

Given the most efficient algorithm you can to find a schedule that maximizes the profits.

Example:

Sample Input : V1     v2   v3    v4    v5   v6   v7   v8

Events ti:   0.1   1.3   2.1  2.2  4.4  4.5  5.1  5.2 

Events gi  5     6     6      3      5