I have thought of this problem, as I was going through such transaction and wished to share it with codeforces community.

Minimum Cost Money Transfer You want to send a total amount of money to a friend using MTN Mobile Money. However, each transaction you make incurs a fixed charge.

You are given a list of intervals, where each interval allows you to send any amount within a specific range at a fixed cost. Your task is to find the minimum total charge needed to send the total amount, by splitting it into valid parts.

Input The input consists of:

An integer x — the total amount to send.

An integer n — the number of available intervals.

Then n lines follow, each containing three integers aᵢ, bᵢ, and cᵢ:

aᵢ and bᵢ are the minimum and maximum values that can be sent in a single transaction using the i-th interval, with 1 ≤ aᵢ ≤ bᵢ .

cᵢ is the charge for each transaction using this interval.

You may use an interval multiple times. You can split the total amount into any number of amount(as long as they sum up to x), and reuse intervals as needed. Note that x falls in one of those intervals but still if you can minimise the cost of sending x amount by splitting it into different amounts which fall under any specific range you may.

Output Print a single integer: the minimum total charge needed to send the full amount x.