Log Throttling

Logs are published in time order. At time t, take the total bytes of logs already published successfully in the closed window [t−window,t]; if adding the current log's size does not exceed bytesLimit, publish it, otherwise drop the whole log. Dropped logs do not use any later quota. Return the total bytes of all successfully published logs, not the indices of the successful logs and not an offline choice of the maximum total.

输入格式

Three lines bytesLimit, window and n in order, followed by n lines of timestamp size. Following the unsigned interface of the original OCR and explicitly adopting the Linux64 model (64-bit Linux), bytesLimit/window/size are all in 0..4294967295 and timestamp is in 0..18446744073709551615. Timestamps are strictly increasing. n is the non-negative number of logs; the original gives no upper bound for it, and this site sets no extra small bound, supporting every valid transmittable instance within the existing 32MiB per-case input budget.

输出格式

Output one non-negative integer, the total bytes actually published; use a 64-bit integer. Zero sizes, a zero limit, a zero window and an empty set of logs are all valid.

样例 1

输入：

10
5
4
0 2
3 4
5 5
7 5

输出：

11

样例 2

输入：

4
1
3
0 3
1 3
2 3

输出：

6

样例 3

输入：

0
0
0

输出：

0

样例说明

The first example comes from the original OCR019: with limit10/window5, sizes 2 and 4 are published at times 0 and 3; the 5 at time 5 would make the closed-window total 11, so it is rejected; the 5 at time 7 is published, for a total of 11. The catalog's edited version returns a list of indices, which disagrees with the real interface in 018, so this site restores the total bytes based on 018–020. The other public examples are derived by this site.