# [TJOI2017]可乐（数据加强版）

## 题目背景

[原题](https://www.luogu.org/problem/P3758) 数据很弱，这个加强版卡掉了暴力的 DP 做法，并且补充了原题题面中缺少的 $\LaTeX$ 。

## 输入输出样例

### 输入样例 #1

3 2
1 2
2 3
2

### 输出样例 #1

8

## 说明

【数据规模与约定】 对于 $20\%$ 的数据， $n,m\leq 30$ ， $t\leq 1000$ ； 对于 $50\%$ 的数据， $t\leq 10^6$； 对于 $100\%$ 的数据， $n,m\leq 100$ ， $t\leq 10^9$ . 【样例解释】 $1$ -> 爆炸 $1$ -> $1$ -> 爆炸 $1$ -> $2$ -> 爆炸 $1$ -> $1$ -> $1$ $1$ -> $1$ -> $2$ $1$ -> $2$ -> $1$ $1$ -> $2$ -> $2$ $1$ -> $2$ -> $3$