Given a list groups with their sizes, their arrival time, and the time to be processed once at the front of the line.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Story

Your park is extremely popular. It’s too popular. You have many individuals complaining about the wait time to enter the park. You want to analyze the time taken to enter the park.

 

You set up an expensive system to track the time at which groups of park patrons arrived, the size of each group, and the time each group took to purchase their tickets once at the front of the line. However, the system stored the data in a strange order, and you need to write a program to analyze the data.

 

There were only 2 ticket counters (left and right) at which to purchase tickets. Both ticket counters had their own line. You know that groups that arrive are good at counting and will always enter the line that has the fewest people. If the 2 lines have the same number of people, then the group enters the “left” line. Once a group entered a line, the group stayed in that line, even if the other line emptied. Once a group is at the front of the line, they begin working on purchasing the tickets, and the time taken is based on given time for that group. If a group is finished being processed at the same time as another group arrives, then the arrival happens first.

 

Your task is to find the sum wait times of each person (not just each group). No two groups arrived at the same time.

 

Problem

Given a list groups with their sizes, their arrival time, and the time to be processed once at the front of the line.

 

Input

Input will begin with a line containing 1 integer, n (1 ≤ n ≤ 500,000), representing the number of groups to process. The following n lines will each contain 3 integers: s, a, and p (1 ≤ s ≤ 1,000,000; 1 ≤ a ≤ 1,000,000,000; 1 ≤ p ≤ 1,000,000) representing the group size, arrival time, and processing time respectively.

 

Output

Output should contain 1 integer representing the sum time taken by all people that waited in line.

 

 

Sample Input Sample Output

4 56

1 4 10

1 2 10

1 1 10

1 3 10

3 65

2 10 10

3 9 1

1 1 20

 

Explanation

Case 1

There are 4 groups. The groups all have 1 person in them. They all take 10 units of time to be processed.

 

The first arriving group is actually the third group in the input. They arrive at time 1. They take 10 units to process. They would finish at time 11. They enter the left line. They took 11 - 1 total time.

 

The second arriving group is the second group in the input. They arrive at time 2. They take 10 units to process. They would finish at time 12. They enter the right line, since the left line has the first arriving group. They took 12 - 2 total time.

 

The third group to arrive is the fourth group in the input. They arrive at time 3. They take 10 units to process, but they won’t be processed until time 11, since 1 is being processed in their line. They finish their process at time 21. They took 21 - 3 total time.

 

The fourth group to arrive is the first group in the input. They arrive at time 4. They take 10 units to process, but they won’t be processed until time 12, since 2 is being processed in their line. They finish their process at time 22. They took 22 - 4 total time.

 

The complete wait time is therefore 56 (10 + 10 + 18 + 18).

 

Below shows pictorially how the groups wait or get processed based on their arrival times.

 

 

Case 2

There are 3 groups.

 

The first group to arrive is the third group in the input. They arrive at time 1. They take 20 units of time to be processed. They will finish at time 21. They have 1 person in their group. The total time they took was 21 - 1 time.

 

The second group to arrive is the second group in input. They have 3 people in their group. They enter the right queue. They take 1 unit of time to be processed. They enter at time 9 and finish at time 10. They have 3 people in their group. The total time they took was 10 - 9 (time taken) times 3 (for each person).

 

The third and last group to arrive is the first group in the input. They have 2 people in their group. They arrive at time 10 and take 10 time units to finish being processed. At that moment there are still 3 people in the right queue, so they enter the left queue, which only has 1 person. They end up waiting until time 21 to be processed. This means that they finish being processed 10 units later at time 31. They contributed 31 - 10 (time taken) times 2 (for each person).

 

 

Attachments:

Expert's Answer

790 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of