P4367 - 【HNOI2015】开店

問題

P4367【HNOI2015】开店

制限 : 時間制限 : - MS メモリ制限 : 524288 KB

審判説明 : 12s,512MB

問題説明

入力形式

如题

出力形式

对于每个方案，输出一行表示方便值。

サンプル入力

10 10 10
0 0 7 2 1 4 7 7 7 9
1 2 270
2 3 217
1 4 326
2 5 361
4 6 116
3 7 38
1 8 800
6 9 210
7 10 278
8 9 8
2 8 0
9 3 1
8 0 8
4 2 7
9 7 3
4 7 0
2 2 7
3 2 1
2 3 4

サンプル出力

1603
957
7161
9466
3232
5223
1879
1669
1282
0

ヒント

对于所有数据，n≤150000，Q≤200000 ，A≤10^9。