Buber is a Berland technology company that specializes in waste of investor's money. Recently Buber decided to transfer its infrastructure to a cloud. The company decided to rent CPU cores in the cloud for 𝑛 consecutive days, which are numbered from 1 to 𝑛 . Buber requires 𝑘 CPU cores each day. The cloud provider offers 𝑚 tariff plans, the 𝑖 -th tariff plan is characterized by the following parameters: 𝑙𝑖 and 𝑟𝑖 — the 𝑖 -th tariff plan is available only on days from 𝑙𝑖 to 𝑟𝑖 , inclusive, 𝑐𝑖 — the number of cores per day available for rent on the 𝑖 -th tariff plan, 𝑝𝑖 — the price of renting one core per day on the 𝑖 -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 𝑐𝑖 ) 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 for 𝑛 days from 1 to 𝑛 . If on a day the total number of cores for all available tariff plans is strictly less than 𝑘 , then this day Buber will have to work on fewer cores (and it rents all the available cores), otherwise Buber rents exactly 𝑘 cores this day.