Problem Description

In the lunchtime rush at a food delivery station, courier Xiao Lan is staring at the screen showing $N$ pending orders. These orders must be delivered strictly in the fixed order listed by the system; they cannot be rearranged or skipped. To complete the task smoothly, Xiao Lan plans to split the $N$ orders into several batches for delivery.

There are $M$ different types of vehicles at the station. Each vehicle has two attributes: average travel time $A_i$ and box crowding coefficient $B_i$. For each batch, Xiao Lan may independently choose the most suitable vehicle from the $M$ types based on the number of orders in that batch.

Suppose a batch contains $L$ orders, and Xiao Lan chooses vehicle type $i$. Then the total time for this batch consists of the following three parts:

1. Travel time: $L \times A_i$ seconds.
2. Pickup/packing time: due to squeezing in the box, arranging $L$ orders requires handling $\frac{L(L-1)}{2}$ pairs of squeezing relationships. Each pair takes $B_i$ seconds, for a total of $\frac{L(L-1)}{2} \times B_i$ seconds.
3. Return time: delivering in batches incurs extra return cost. When processing the first batch, since Xiao Lan is assumed to have already loaded at the station and can depart directly, this part takes $0$ seconds. Starting from the second batch, each time a new batch is started, a fixed $X$ seconds must be spent to return to the station to load the next batch.

Now, please help Xiao Lan plan an optimal batching scheme and compute the minimum total time needed to finish delivering all $N$ orders.

Input Format

The first line contains three integers $N$, $M$, and $X$, representing the total number of orders, the number of vehicle types, and the fixed time cost.

The next $M$ lines each contain two integers $A_i$ and $B_i$, representing the average travel time and the box crowding coefficient of the $i$-th vehicle type.

Output Format

Output one integer, the minimum total time required to complete delivery of all $N$ orders (in seconds).

5 2 40
10 8
2 20

118

Hint

Sample Explanation

One optimal plan is to split into $2$ batches:

Constraints

For $30\%$ of the testdata, $1 \le N, M \le 100$.

For all testdata, $1 \le N, M \le 5000$, $1 \le X, A_i, B_i \le 10^9$.

Translated by ChatGPT 5