JOI国有 $N$ 个城市，编号从 $1$ 到 $N$ ；另外，有 $N−1$ 条铁路，编号从 $1$ 到 $N−1$ ，其中第 $i$ 条 $(1\le i\le N-1)$ 铁路双向连接城市 iii 和城市 $i+1$ 。
乘坐 JOI 国家的铁路有两种方法：用纸质车票乘车或用 IC 卡乘车。
用纸质车票在铁路 $i$ 上乘车的费用为 $A_i$ ，用 IC 卡在铁路 $i$ 上乘车的费用为 $B_i$ 。但是要用 IC 卡在铁路铁路 $i$ 上乘车，必须先购买铁路 $i$ 可以使用的 IC 卡。购买铁路 $i$ 可以使用的 IC 卡需要 $C_i$ 日元。购买一次 IC 卡就可以多次使用。
由于 IC 卡的金额处理比较简单，所以用 IC 卡乘车时的费用比用纸质车票乘车时的费用便宜。也就是说，对于所有 $1 \le i \le n-1$ ，都满足 $A_i \gt B_i$ 。由于 IC 卡的规定在每条铁路上都不同，所以对于所有 $1 \le i \le n-1$ ，不能在其他铁路上使用铁路 $i$ 可以使用的 IC 卡。
您决定在 JOI 国旅行。从城市 $P_1$ 出发，按照 $P_2,P_3...P_M$ 的顺序访问城市。旅行由 $M−1$ 天的行程组成。其中，在第 $j$ 天 $(1\le j\le M-1)$ ，在铁路上乘车从城市 $P_j$ 移动到城市$P_{j+1}$ 。此时，你可能在不同的铁路上乘车。另外，你可能会去同一个城市两次及以上。
JOI 国的铁路很快，所以你从任意一个城市乘车到任意一个城市只需要一天。现在，你没有任何铁路的 IC 卡。你可以选择预先购买一些铁路的 IC 卡，减少花费在乘车上的费用。
也就是说，你需要规划是否购买 IC 卡，使得购买 IC 卡的费用和乘车费用之和最小。