X星球的居民點很多。Pear決定修建一個浩大的水利工程，以解決他管轄的N個居民點的供水問題?，F(xiàn)在一共有N個水塔，同時也有N個居民點，居民點在北側(cè)從1號到N號自西向東排成一排；水塔在南側(cè)也從1號到N號自西向東排成一排。

    N條單向輸水線（有水泵動力），將水從南側(cè)的水塔引到北側(cè)對應(yīng)的居民點。

    我們不妨將居民點和水塔都看做平面上的點，居民點坐標(biāo)為(1,K)~(N,K)，水塔為(1,0)~(N,0)。

    除了N條縱向輸水線以外，還有M條單向的橫向輸水線，連接(Xi,Yi)和(Xi,(Yi)+1)或者(Xi,Yi)和(Xi,(Yi)-1)。前者被稱為向右的水路，而后者是向左的。不會有兩條水路重疊，即便它們方向不同。

    布局的示意圖如：【p1.png】所示。

    顯然，每個水塔的水都可以到達(dá)若干個居民點（而不僅僅是對應(yīng)的那個）。例如上圖中，4號水塔可以到達(dá)3、4、5、6四個居民點。

    現(xiàn)在Pear決定在此基礎(chǔ)上，再修建一條橫向單向輸水線。為了方便考慮，Pear認(rèn)為這條水路應(yīng)當(dāng)是自左向右的，也就是連接了一個點和它右側(cè)的點（例如上圖中連接5和6兩個縱線的橫向水路）。

    Pear的目標(biāo)是，修建了這條水路之后，能有盡可能多對水塔和居民點之間能到達(dá)。換句話說，設(shè)修建之后第i個水塔能到達(dá)Ai個點，你要最大化A1+A2+...+An。

    根據(jù)定義，這條路必須和X軸平行，但Y坐標(biāo)不一定要是整數(shù)。注意：雖然輸入中沒有重疊的水路，但是你的方案可以將新修的輸水線路與已有的水路重疊。

 輸入第一行包含三個正整數(shù)N，M，K，含義如題面所述：N是縱向線數(shù)，M橫向線數(shù)，K是居民點縱坐標(biāo)。

    接下來M行，每行三個整數(shù)。前兩個正整數(shù)Xi Yi表示水路的起點坐標(biāo)；
    1<=Xi<=N,0<Yi<K。
    接下來一個數(shù)0或者1，如果是0表示這條水路向左，否則向右。
    保證水路都是合法的，也就是不會流向沒有定義的地方。

輸出一行。是一個正整數(shù)，即：題目中要求的最大化的A1+A2+...+An。

零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點擊這里了解課程詳情

藍(lán)橋杯