high way

In the year 2100, human finally finish building a high-speed railway, which connects each country in the world(It’s not a circle but a line). There are $N$ countries in the world, but the relationships between each countries are not very good, so if teacherone wants to take a train from one country to another, he must buy tickets for each segment of the railway seperately. For example, if he wants to go to country $i+2$ from country $i$, he needs to spend $Ai$ RMB for $i$ to $i+1$ and $Ai+1$ RMB for $i+1$ to $i+2$. This rediculous policy causes lots of unconviniences for the people arround the world. Thus those countries, which are running this railway service made a policy: One can spend $Bi$ RMB to buy a card and pop up money into the card, then use the money in the card to take the train. And people who uses the card just need to pay $Ci$ RMB for the trip($Ci$<$Bi$). The card can be bought from the Internet (One doesn’t need to buy it in the station). Also, because of the bad relationship, one needs to buy the card seperately for one segment of railway.

Now Teacherone has a travel plan, he wants to go to $M$ places. He starts from $P_1$ and go to $P_2$, and $P_2$ to $P_3$ …. He wants to spend money as little as he can, so he finds you to ask for help. Please help him figure out the minimum amount of money that he will spend.

Input:

The first line contains two positive integers N, M

The second line contains M numbers represents $P_i$

Last N-1 lines contains three integers for each, represents $A_i$, $B_i$ and $C_i$ for the $i^th$ segment of railway service.

Output:

A single line contains the minimum amount of money that teacherone will spend.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define lson(x) x<<1
#define rson(x) x<<1|1
#define MID(x,y) (x+y)>>1
#define bk break
typedef long long ll;
typedef void V;


ll A[100010],B[100010],C[100010];
int N,K;
int q;
int M,T;

inline long long read(){ 
    char ch;
    bool flag = false;
    int a=0;
    while(!((((ch=getchar())>='0') && (ch<='9')) || (ch=='-')));
    if(ch!='-'){
        a *= 10;
        a += ch - '0';
    }
    else{
        flag = true;
    }
    while(((ch=getchar())>='0')&& (ch<='9')){
        a *= 10;
        a += ch - '0';
    }
    if(flag){
        a = -a;
    }
    return a;
}
ll G[100010<<1];
ll num[100010<<1], sum[100010<<1], add[100010<<1], v;

void pushDown(int i, int l, int r) {
    if(add[i] != 0) {
        int mid=MID(l,r);
        add[lson(i)]+=add[i];
        sum[lson(i)]+=(mid-l+1)*add[i];
        add[rson(i)]+=add[i];
        sum[rson(i)]+=(r-mid)*add[i];
        add[i]=0;
    }
}

void update(int i, int l, int r, int ql, int qr, int val) {
    if(l>qr || ql>r)
        return;
    if(l>=ql && r<=qr){
        sum[i]+=(r-l+1)*val;
        add[i]+=val;
        return ;
    }
    pushDown(i,l,r);
    int mid=MID(l,r);
    update(lson(i),l,mid,ql,qr,val);
    update(rson(i),mid+1,r,ql,qr,val);
    sum[i]=sum[lson(i)]+sum[rson(i)];
}

ll query(int i,int l,int r,int ql,int qr) {
    if(l>qr || ql>r)
        return 0;
    if(l>=ql && r<=qr)
        return sum[i];
    pushDown(i,l,r);
    int mid=MID(l,r);
    return query(lson(i),l,mid,ql,qr)
    + query(rson(i),mid+1,r,ql,qr);
}

int main(){
    N=read();M=read();
    for(int i=1;i<=M;++i){
        G[i]=read();
    }
    for(int i=1;i<M;++i){
        int b,e;
        b=G[i];e=G[i+1];
        if(b>e) swap(b,e);
        update(1,1,N,b,e-1,1); // Interval Update
    }
    long long Ai,Bi,Ci;
    long long ans=0;
    for(int i=1;i<=N-1;++i){
        Ai=read();Bi=read();Ci=read();
        ll t = query(1,1,N,i,i);
        ans+=min(Ai*t,Bi*t+Ci);
    }
    cout<<ans;
    return 0;
}

###

###