I recently interviewed with IBM for a backend developer role. The experience was challenging, with a 45-minute session featuring complex questions on segment tree algorithms and SQL.

Despite the difficulty, I found the time constraint for entry-level positions to be insufficient, leading to a negative overall experience.

Buber is a Berland technology company that specializes in wasting investor money. Recently, Buber decided to transfer its infrastructure to the cloud. The company decided to rent CPU cores in the cloud for n consecutive days, numbered from 1 to n. Buber requires k CPU cores each day.

The cloud provider offers m tariff plans. The i-th tariff plan is characterized by the following parameters:

• l_i and r_i: The i-th tariff plan is available only on days from l_i to r_i, inclusive.
• c_i: The number of cores per day available for rent on the i-th tariff plan.
• p_i: The price of renting one core per day on the i-th tariff plan.

Buber can arbitrarily share its computing core needs between the tariff plans. Every day, Buber can rent an arbitrary number of cores (from 0 to c_i) on each of the available plans. The number of rented cores on a tariff plan can vary arbitrarily from day to day.

Find the minimum amount of money that Buber will pay for its work over n days. If, on a given day, the total number of cores available from all tariff plans is strictly less than k, Buber will have to work on fewer cores (and it will rent all available cores). Otherwise, Buber rents exactly k cores that day.