using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("4 3");
WillReturn.Add("20 10 100 10");
WillReturn.Add("1 3 100");
WillReturn.Add("2 4 50");
WillReturn.Add("1 1 50");
//70
}
else if (InputPattern == "Input2") {
WillReturn.Add("2 2");
WillReturn.Add("10 10");
WillReturn.Add("1 1 1000");
WillReturn.Add("1 2 100");
//0
}
else if (InputPattern == "Input3") {
WillReturn.Add("20 10");
WillReturn.Add("40 28 12 29 34 89 37 64 48 53 81 95 46 42 77 76 49 59 14 15");
WillReturn.Add("2 11 221");
WillReturn.Add("14 20 14");
WillReturn.Add("2 11 126");
WillReturn.Add("1 8 273");
WillReturn.Add("5 11 94");
WillReturn.Add("2 8 48");
WillReturn.Add("12 15 83");
WillReturn.Add("2 7 13");
WillReturn.Add("5 16 269");
WillReturn.Add("3 12 115");
//760
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long mGoalInd;
struct EdgeInfoDef
{
internal long ToNode;
internal long Cost;
}
static Dictionary<long, List<EdgeInfoDef>> mEdgeInfoListDict = new Dictionary<long, List<EdgeInfoDef>>();
static void Main()
{
List<string> InputList = GetInputList();
long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
long[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
mGoalInd = AArr.GetUpperBound(0) + 1;
Action<long, long, long> AddEdgeAct = (pFromNode, pToNode, pCost) =>
{
EdgeInfoDef WillAdd;
WillAdd.ToNode = pToNode;
WillAdd.Cost = pCost;
mEdgeInfoListDict[pFromNode].Add(WillAdd);
};
for (long I = 0; I <= AArr.GetUpperBound(0); I++) {
mEdgeInfoListDict[I] = new List<EdgeInfoDef>();
// 宝箱の解錠を諦める経路
AddEdgeAct(I, I + 1, AArr[I]);
// 1つ前に戻る経路
if (0 < I) {
AddEdgeAct(I, I - 1, 0);
}
}
foreach (string EachStr in InputList.Skip(2)) {
SplitAct(EachStr);
long L = wkArr[0] - 1;
long R = wkArr[1] - 1;
long C = wkArr[2];
// 区間の宝箱を解錠する経路
AddEdgeAct(L, R + 1, C);
}
long ScoreMax = AArr.Sum();
Dictionary<long, long> Result = Dijkstra(0);
Console.WriteLine(ScoreMax - Result[mGoalInd]);
}
// ダイクストラ法で、各ノードまでの最短距離を求める
static Dictionary<long, long> Dijkstra(long pStaNode)
{
var InsPQueue = new PQueue_Arr();
// 距離合計[確定ノード]なDict
var KakuteiNodeDict = new Dictionary<long, long>();
KakuteiNodeDict.Add(pStaNode, 0);
//Enqueue処理
Action<long> EnqueueAct = pFromNode =>
{
if (mEdgeInfoListDict.ContainsKey(pFromNode) == false) {
return;
}
foreach (EdgeInfoDef EachEdge in mEdgeInfoListDict[pFromNode]) {
// 確定ノードならContinue
if (KakuteiNodeDict.ContainsKey(EachEdge.ToNode)) continue;
long wkSumCost = KakuteiNodeDict[pFromNode] + EachEdge.Cost;
PQueue_Arr.PQueueJyoutaiDef WillEnqueue;
WillEnqueue.Node = EachEdge.ToNode;
WillEnqueue.SumCost = wkSumCost;
InsPQueue.Enqueue(WillEnqueue);
}
};
EnqueueAct(pStaNode);
while (InsPQueue.IsEmpty() == false) {
PQueue_Arr.PQueueJyoutaiDef Dequeued = InsPQueue.Dequeue();
// 確定ノードならcontinue
if (KakuteiNodeDict.ContainsKey(Dequeued.Node)) continue;
// 枝切り
if (KakuteiNodeDict.ContainsKey(mGoalInd)) break;
KakuteiNodeDict.Add(Dequeued.Node, Dequeued.SumCost);
EnqueueAct(Dequeued.Node);
}
return KakuteiNodeDict;
}
}
#region PQueue_Arr
// 内部で配列使用の優先度付きキュー
internal class PQueue_Arr
{
internal struct PQueueJyoutaiDef
{
internal long Node;
internal long SumCost;
}
private PQueueJyoutaiDef[] mHeapArr;
private long mHeapArrCnt = 0;
// コンストラクタ
internal PQueue_Arr()
{
mHeapArr = new PQueueJyoutaiDef[65535];
}
internal bool IsEmpty()
{
return mHeapArrCnt == 0;
}
// エンキュー処理
internal void Enqueue(PQueueJyoutaiDef pAddJyoutai)
{
long CurrNode = 1 + mHeapArrCnt;
if (mHeapArr.GetUpperBound(0) < CurrNode) {
ExtendArr();
}
mHeapArr[CurrNode] = pAddJyoutai;
mHeapArrCnt++;
while (1 < CurrNode && mHeapArr[CurrNode / 2].SumCost > mHeapArr[CurrNode].SumCost) {
PQueueJyoutaiDef Swap = mHeapArr[CurrNode];
mHeapArr[CurrNode] = mHeapArr[CurrNode / 2];
mHeapArr[CurrNode / 2] = Swap;
CurrNode /= 2;
}
}
// 配列のExtend
private void ExtendArr()
{
PQueueJyoutaiDef[] NewHeapArr = new PQueueJyoutaiDef[mHeapArrCnt * 2];
mHeapArr.CopyTo(NewHeapArr, 0);
mHeapArr = NewHeapArr;
}
// デキュー処理
internal PQueueJyoutaiDef Dequeue()
{
PQueueJyoutaiDef TopNode = mHeapArr[1];
long LastNode = mHeapArrCnt;
mHeapArr[1] = mHeapArr[LastNode];
mHeapArrCnt--;
MinHeapify(1);
return TopNode;
}
// 根ノードを指定し、根から葉へヒープ構築
private void MinHeapify(long pRootNode)
{
if (mHeapArrCnt <= 1) {
return;
}
long Left = pRootNode * 2;
long Right = pRootNode * 2 + 1;
// 左の子、自分、右の子で値が最小のノードを選ぶ
long Smallest = mHeapArr[pRootNode].SumCost;
long SmallestNode = pRootNode;
if (Left <= mHeapArrCnt && mHeapArr[Left].SumCost < Smallest) {
Smallest = mHeapArr[Left].SumCost;
SmallestNode = Left;
}
if (Right <= mHeapArrCnt && mHeapArr[Right].SumCost < Smallest) {
Smallest = mHeapArr[Right].SumCost;
SmallestNode = Right;
}
// 子ノードのほうが大きい場合
if (SmallestNode != pRootNode) {
PQueueJyoutaiDef Swap = mHeapArr[SmallestNode];
mHeapArr[SmallestNode] = mHeapArr[pRootNode];
mHeapArr[pRootNode] = Swap;
// 再帰的に呼び出し
MinHeapify(SmallestNode);
}
}
}
#endregion