using System.Runtime.CompilerServices;
using System.Numerics;
using System.Runtime.InteropServices;
using System.Net;


namespace test
{
    internal class Program
    {
        static void Main(string[] args)
        {
            cin = new input();
            //mod = new mod(998244353);
            toolbox = new toolbox();
            Priority_Queue = new Priority_Queue(true);
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            toolbox.StartTimer();

            int n=cin.intreed();
            int m=cin.intreed();
            var arr=cin.arrayint(n);
            var eage=new List<(int from,int next,long cost)>();
            for(int i=0; i<m; i++)
            {
                int u=cin.intreed();
                int v=cin.intreed();
                long cost=cin.intreed();
                eage.Add((u,v,-(arr[v-1]-cost)));
            }

            var g=Enumerable.Repeat(0,n+1).Select(_=>new List<(int next,long cost)>()).ToList();
            foreach(var (from,next,cost) in eage)
                g[next].Add((from,0));

            //まず、逆向きグラフで終点から到着な頂点集合を作って、補集合を無視する
            var seen=new HashSet<int>();
            seen.Add(n);
            dfs(n);
            void dfs(int now)
            {
                foreach(var (next,_) in g[now])
                    if(!seen.Contains(next))
                    {
                        seen.Add(next);
                        dfs(next);
                    }
            }

            var spfa=new SPFA(n+1,false);
            eage.Add((n+1,1,-arr[0]));
            foreach(var (from,next,cost) in eage)
                if(seen.Contains(next))
                    spfa.Connect_Graph(from,next,cost);
            
            if(spfa.Start_SPFA(n+1))
                System.Console.WriteLine(spfa.dist[n]*-1);
            else
                System.Console.WriteLine("inf");


            toolbox.PrintElapsedTime();
            Console.Out.Flush();
        }
        static input cin;
        static mod mod;
        static toolbox toolbox;
        static Priority_Queue Priority_Queue;
    }


    internal class SPFA
    {
        private Queue<long> que;
        public long[] dist { get; set; }
        public bool interactive { get; set; }
        public List<List<(int next, long cost)>> Graph { get; set; }
        
        public List<long> len { get; set; }//始点からその頂点までの現在見つかっている最短経路の辺数を数える もし負閉路が存在しないなら、これは全頂点数を超えない
        public List<bool> pending { get; set; }

        public SPFA(int n, bool cnt = true)
        {
            que = new Queue<long>();
            dist = Enumerable.Repeat<long>(long.MaxValue, n + 1).ToArray();
            len = Enumerable.Repeat<long>(0, n + 1).ToList();
            pending = Enumerable.Repeat<bool>(false, n + 1).ToList();
            Graph = new List<List<(int, long)>>();
            for (int i = 0; i <= n; i++)
            {
                Graph.Add(new List<(int, long)>());
            }
            interactive = cnt;
        }

        public void Connect_Graph(int i, int t, long cost)
        {
            //(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
            Graph[i].Add((t, cost));
            if (interactive)
                Graph[t].Add((i, cost));
        }

        public bool Start_SPFA(int i)
        {
            //(捜索を始める頂点(int))
            que.Enqueue(i);
            pending[i] = true;
            dist[i] = 0;
            len[i]=0;
            while (que.Count != 0)
            {
                var t = (int)que.Dequeue();
                pending[t] = false;
                for (int w = 0; w < Graph[t].Count; w++)
                {
                    long cost_before = dist[t] + Graph[t][w].Item2;
                    if (dist[Graph[t][w].Item1] <= cost_before)
                        continue;
                    dist[Graph[t][w].Item1] = cost_before;
                    if((len[Graph[t][w].Item1]=len[t]+1)>=Graph.Count-1)//1indexなので1つズレてる 超頂点とか倍化すると検出が遅れるが、検出自体は壊れないはず
                        return false;//負閉路
                    if (!pending[(int)Graph[t][w].Item1])
                    {
                        que.Enqueue(Graph[t][w].Item1);
                        pending[(int)Graph[t][w].Item1] = true;
                    }
                }
            }
            return true;//負閉路はない
        }
    }





    public class ThisIsNotAWavelet_Matrix<T1>
        where T1 : struct, IComparable
    {
        //1index!!
        //クエリの失敗は-1またはstatus==false

        public class Compress<T2>
            where T2 : struct, IComparable
        {
            //1indexだよ!!!! 例[1,5,8,9,5,5]=>[1,2,3,4,2,2]
            public Dictionary<int, T2> key2raw;
            public Dictionary<T2, int> raw2key;
            //やりたいこと　構築　生=>圧縮後　圧縮後=>生
            public Compress(IEnumerable<T2> vector = null)
            {
                key2raw = new Dictionary<int, T2>();
                raw2key = new Dictionary<T2, int>();
                if (vector is { })
                    Build(vector);
            }

            public (List<int>, IOrderedEnumerable<T2>) Build(IEnumerable<T2> vector)
            {
                int cnt = 0;
                var back = new List<int>();
                var sorted = vector.OrderBy(i => i);
                foreach (var i in sorted)
                {
                    if (!raw2key.ContainsKey(i))
                    {
                        cnt++;
                        raw2key.Add(i, cnt);
                        key2raw.Add(cnt, i);
                    }
                }
                foreach (var i in vector)
                    back.Add(raw2key[i]);
                return (back, sorted);
            }

            //インデクサは圧縮後=>生
            public T2 this[int k] => key2raw[k];
            public int Count => key2raw.Count;
        }

        public class SegmentTree
        {
            //たまには1indexで書いてみたくないですか？　書きたい
            //とりあえずrange sum
            internal struct node
            {
                //index=0のnodeはnullを表す
                public int val;
                public int left;
                public int right;
                public node(int a) => val = a;
                public node()
                {
                    val = 0;
                    left = 0;
                    right = 0;
                }
            }

            public List<int> roots;//roots[i]=>バージョンiのrootのインデックス　root[0]は0が入っている
            internal node[] nodes;
            internal int size;

            private int now_index;
            //5*1e5回のsetをすると、nodesizeは2*1e7でギリギリ(400MB程度) 5*1e7でも速度的には大丈夫だけど、メモリがやばい(900MBギリ下回るぐらい)　
            public SegmentTree(int n, int nodesize = 5 * (int)1e7)
            {
                size = 1;
                while (size < n) size <<= 1;
                nodes = Enumerable.Repeat(new node(), nodesize).ToArray();
                now_index = 2;
                roots = [0, 1];
            }


            public int add(int val, int index, int version = 1)
            {
                int root = add(val, index, roots[version], 1, size + 1);
                if (root == -1) return -1;
                roots.Add(root);
                return roots.Count - 1;
            }
            /// <summary>
            /// 
            /// </summary>
            /// <param name="val">代入する値</param>
            /// <param name="index">代入する位置(1index)</param>
            /// <param name="node_index">現在のノード</param>
            /// <param name="l">現在のノードが担当する範囲の左側(閉区間)</param>
            /// <param name="r">右側(開区間)</param>
            /// <returns>更新後の木のversion</returns>
            private int add(int val, int index, int node_index, int l, int r)
            {
                if (index < l || r <= index) return -1;
                int now = newnode();
                nodes[now] = nodes[node_index];
                if (l + 1 == r)
                {
                    nodes[now].val += val;
                    return now;
                }
                int mid = (l + r) >> 1;
                if (index < mid)
                {
                    int left = add(val, index, nodes[node_index].left, l, mid);
                    if (left == -1) return -1;
                    nodes[now].left = left;
                }
                else
                {
                    int right = add(val, index, nodes[node_index].right, mid, r);
                    if (right == -1) return -1;
                    nodes[now].right = right;
                }
                nodes[now].val = nodes[nodes[now].left].val + nodes[nodes[now].right].val;
                return now;
            }
            /// <summary>
            /// [l,r)
            /// </summary>
            /// <param name="l"></param>
            /// <param name="r"></param>
            /// <param name="version"></param>
            /// <returns></returns>
            public int query(int l, int r, int version = 1) => query(l, r, roots[version], 1, size + 1);

            private int query(int a, int b, int node_index, int l, int r)
            {
                if (node_index == 0) return 0;//nullノード
                if (b <= l || r <= a) return 0;//範囲外
                if (a <= l && r <= b) return nodes[node_index].val;//完全被覆
                int mid = (l + r) >> 1;
                int left = query(a, b, nodes[node_index].left, l, mid);
                int right = query(a, b, nodes[node_index].right, mid, r);
                return left + right;
            }
            /// <summary>
            /// 1index
            /// </summary>
            /// <param name="index"></param>
            /// <param name="version"></param>
            /// <returns></returns>
            public int get(int index, int version = 1)
            {
                int l = 1;
                int r = size + 1;
                int now = roots[version];
                while (true)
                {   
                    if(now==0)
                        return 0;//nullノード
                    if (index < l || r <= index) return 0;
                    if (l + 1 == r)
                        return nodes[now].val;
                    int mid = (l + r) >> 1;
                    if(index<mid)
                    {
                        now=nodes[now].left;
                        r=mid;
                    }
                    else
                    {
                        now=nodes[now].right;
                        l=mid;
                    }
                }
            }

            private int newnode() => now_index++;

        }
        public SegmentTree tree;
        public Compress<T1> comp;
        public List<T1> rows;//重複を排除した座標圧縮前の配列の要素全て(ソート済み)
        private const int NodePoolMargin = 100;
        public ThisIsNotAWavelet_Matrix(IEnumerable<T1> arr)
        {
            //座標圧縮してから構築する
            comp = new Compress<T1>();
            var comped = comp.Build(arr);
            int nodesize = GetNodePoolSize();
            tree = new SegmentTree(comp.Count + 1,nodesize);
            int version = 1;
            foreach (var i in comped.Item1)
            {
                version = tree.add(1, i, version);
            }
            rows = comped.Item2.Distinct().ToList();
            int GetNodePoolSize()
            {
                int n = comped.Item1.Count;
                int k = comp.Count+1;
                int size = 1;
                int height = 0;
                while (size < k)
                {
                    size <<= 1;
                    height++;
                }
                height++;
                return 2 + n * height + NodePoolMargin;//2(nullと初期ノード)+n*(add1回で作らないといけないノード数<=>木の高さ)+マージン
            }
        }
        //区間[a,b)でk番目に大きい値を取得する
        public (T1, bool status) GetKthLargest(int a, int b, int k)
        {
            //root[b]とroot[a]を見比べればいい varsion=1は全て0の状態　version=2がarrの最初の要素を入れた状態であることに注意せよ　つまり、versionは1ずれている
            if (a < 1 || b < 1 || a >= b) return (default, false);//区間が不正
            if (b > tree.roots.Count - 1) return (default, false);//範囲外
            long total = tree.nodes[tree.roots[b]].val - tree.nodes[tree.roots[a]].val;
            if (k <= 0 || total < k) return (default, false);//そんな要素ないです

            //今見てるノード
            int node_a = tree.roots[a];
            int node_b = tree.roots[b];
            //今見てる区間
            int l = 1;
            int r = tree.size + 1;

            while (l + 1 != r)
            {
                int left_a = tree.nodes[node_a].left;
                int left_b = tree.nodes[node_b].left;
                int right_a = tree.nodes[node_a].right;
                int right_b = tree.nodes[node_b].right;
                int cnt_right = tree.nodes[right_b].val - tree.nodes[right_a].val;//この区間の右側にある要素数
                int mid = (l + r) >> 1;

                if (cnt_right >= k)
                {
                    node_a = right_a;
                    node_b = right_b;
                    l = mid;
                }
                else
                {
                    k -= cnt_right;
                    node_a = left_a;
                    node_b = left_b;
                    r = mid;
                }
            }
            return (comp[l], true);
        }
        //区間[a,b)でk番目に小さい値を返す
        public (T1, bool) GetKthSmallest(int a, int b, int k)
        {
            if (a < 1 || b < 1 || a >= b) return (default, false);//区間が不正
            if (b > tree.roots.Count - 1) return (default, false);//範囲外
            int total = tree.nodes[tree.roots[b]].val - tree.nodes[tree.roots[a]].val;
            if (k <= 0 || total < k) return (default, false);//そんな要素ないです
            return GetKthLargest(a, b, total - k + 1);//k番目に大きい値に変更して投げる
        }
        //区間[a,b)の要素で[x,y)を満たすものの要素を数える　a,b,x,yのどれかが不正だと壊れるよ
        public int RangeFreq(int a, int b, T1 x, T1 y) => CountLower(a, b, y) - CountLower(a, b, x);
        //区間[a,b)の要素でx未満の要素の数を数える
        public int CountLower(int a, int b, T1 x)
        {
            if (a < 1 || b < 1 || a >= b) return -1;//区間が不正
            if (b > tree.roots.Count - 1) return -1;//範囲外
            int x_comped = rows.BinarySearch(x);
            if (x_comped < 0) x_comped = ~x_comped;
            x_comped++;
            int l = tree.query(1, x_comped, a);//[1,a)でのクエリ結果
            var r = tree.query(1, x_comped, b);//[1,b)でのクエリ結果
            //xを圧縮後の世界に飛ばす　x未満を数えるから、xを超える最小値を探してきて、それでいい

            return r - l;//[1,b)-[1,a)=[a,b)
        }
        //区間[a,b)でx未満の最大値を返す
        public (T1, bool status) PrevValue(int a, int b, T1 x)
        {
            //サボり実装
            int cnt = CountLower(a, b, x);//区間[a,b)でx未満の個数を数える
            if (cnt <= 0) return (default, false);
            return GetKthSmallest(a, b, cnt);//求める値はcnt番目に小さいもの
        }
        //区間[a,b)でx以上の最小値を返す
        public (T1, bool status) NextValue(int a, int b, T1 x)
        {
            int cnt = CountLower(a, b, x);//区間[a,b)でx未満の個数を数える
            if (cnt < 0) return (default, false);
            return GetKthSmallest(a, b, cnt + 1);//cnt+1はx以上になる最初の値の順位
        }
        //区間[1,b)でxが登場する回数を返す
        public int Count(int b, T1 x)
        {
            var index = rows.BinarySearch(x);
            if (index < 0)
                return 0;//xは1度も登場しない
            index++;
            return tree.get(index, b);
        }
        //区間[a,b)でxが登場する回数を返す
        public int Count(int a, int b, T1 x) => Count(b, x) - Count(a, x);
        //区間[a,b)で要素xがi回目に登場するインデックスを返す 計算量O(logN*log(種類数))
        public int Select(int a, int b, T1 x, int cnt)
        {
            //xは座標圧縮後であることに注意せよ
            int Count(int a, int b, int x) => tree.get(x, b) - tree.get(x, a);

            if (a < 1 || b < 1 || a >= b) return -1;//区間が不正
            if (b > tree.roots.Count - 1) return -1;//範囲外
            if (cnt <= 0) return -1;
            var index = rows.BinarySearch(x);
            if (index < 0) return -1;//そんな要素存在しない
            index++;
            int total = Count(a, b, index);
            if (total < cnt) return -1;

            int l = a;
            int r = b;
            while (l + 1 < r)
            {
                int mid = (l + r) >> 1;
                int left = Count(l, mid, index);
                if (left >= cnt)
                {
                    r = mid;
                }
                else
                {
                    l = mid;
                    cnt -= left;
                }
            }
            return l;
        }
    }

    public static class Extensions
    {
        public static Dictionary<T, int> safe_addtion_for_dictionary_int<T>(this Dictionary<T, int> dic, T key)
        {
            if (dic.ContainsKey(key))
                dic[key]++;
            else
                dic.Add(key, 1);
            return dic;
        }

        public static Dictionary<T, long> safe_addtion_for_dictionary_long<T>(this Dictionary<T, long> dic, T key)
        {
            if (dic.ContainsKey(key))
                dic[key]++;
            else
                dic.Add(key, 1);
            return dic;
        }

        public static Dictionary<T, List<T2>> safe_addtion_for_list_in_dictionary<T, T2>(this Dictionary<T, List<T2>> dic, T key, T2 value)
        {
            if (dic.ContainsKey(key))
                dic[key].Add(value);
            else
                dic.Add(key, new List<T2>() { value });
            return dic;
        }

        public static T list_pop_back<T>(this List<T> a)
        {
            var k = a[a.Count - 1];
            a.RemoveAt(a.Count - 1);
            return k;
        }

        public static T chmin<T>(ref this T a, T b)
            where T : struct, IComparable
        {
            if (a.CompareTo(b) > 0)
                return a = b;
            else
                return a;
        }
        public static T chmax<T>(ref this T a, T b)
            where T : struct, IComparable
        {
            if (a.CompareTo(b) < 0)
                return a = b;
            else
                return a;
        }

    }

    internal class input
    {
        string[] soloinput;
        int t;
        public input()
        {
            soloinput = new string[0];
            t = 0;
        }
        public string soloreed()
        {
            if (t < soloinput.Length)
            {
                return soloinput[t++];
            }
            string input = Console.ReadLine();
            while (input == "")
            {
                input = Console.ReadLine();
            }
            soloinput = input.Split(" ");
            t = 0;
            return soloinput[t++];
        }
        public int intreed()
        {
            return int.Parse(soloreed());
        }
        public int[] arrayint(int N)
        {
            int[] A = new int[N];
            for (int i = 0; i < N; i++)
            {
                A[i] = intreed();
            }
            return A;
        }
        public long longreed()
        {
            return long.Parse(soloreed());
        }
        public long[] arraylong(long N)
        {
            long[] A = new long[N];
            for (long i = 0; i < N; i++)
            {
                A[i] = longreed();
            }
            return A;
        }
        public decimal decimalreed()
        {
            return decimal.Parse(soloreed());
        }
        public decimal[] arraydecimal(long N)
        {
            decimal[] A = new decimal[N];
            for (decimal i = 0; i < N; i++)
            {
                A[(long)i] = decimalreed();
            }
            return A;
        }


    }

    internal class mod
    {
        public long T { get; set; }
        public mod(long mod = 1000000007)
        {
            T = mod;
        }
        public long addition(long A, long B)
        {
            long C = A + B;
            return (long)C % T;
        }
        public long subtraction(long A, long B)
        {
            return ((A % T) - (B % T) + T) % T;
        }
        public long multiplication(long A, long B)
        {
            return ((A % T) * (B % T)) % T;
        }

    }

    internal class toolbox
    {

        string Y = "Yes";
        string N = "No";
        static input cin;
        private DateTime? startTime;
        public toolbox()
        {
            cin = new input();
        }

        public long[] CumulativeSum(long[] A, bool mode = true)
        {
            if (mode == false) Array.Reverse(A);
            long[] back = new long[A.Length + 1];
            back[0] = 0;
            for (int i = 1; i <= A.Length; i++)
            {
                back[i] = back[i - 1] + A[i - 1];
            }
            if (mode == false) Array.Reverse(A);
            return back;
        }

        public long[] Eratosthenes(long A)
        {
            A++;
            var back = new List<long>();
            bool[] ch = new bool[A];
            for (int i = 2; i < A; i++) ch[i] = true;
            for (long i = 2; i < Math.Sqrt(A); i++)
            {
                if (ch[i] == true)
                {
                    back.Add(i);
                    for (long t = 1; i * t < A; t++)
                    {
                        ch[i * t] = false;
                    }
                }
            }
            for (long i = 0; i < A; i++)
            {
                if (ch[i] == true) back.Add(i);
            }
            return back.Distinct().ToArray();
        }
        public void Swap<T>(ref T a, ref T b)
        {
            var i = a;
            a = b;
            b = i;
        }

        public void LSwap<T>(ref List<T> A, int a, int b)
        {
            var i = A[a];
            A[a] = A[b];
            A[b] = i;
        }

        public long Gcd(long A, long B)
        {
            while (A != 0)
            {
                B %= A;
                Swap(ref A, ref B);
            }
            return B;
        }

        public long[] AllDivisors(long N)
        {
            var back = new List<long>();
            for (int i = 1; Math.Pow(i, 2) <= N; i++)
            {
                if (N % i == 0)
                {
                    back.Add(i);
                    back.Add(N / i);
                }
            }
            return back.Distinct().ToArray();
        }

        public static IEnumerable<T[]> ExhaustiveEnumeration<T>(IEnumerable<T> indata)
        {
            if (indata.Count() == 1) yield return new T[] { indata.First() };
            foreach (var i in indata)
            {
                var used = new T[] { i };
                var unused = indata.Except(used);
                foreach (var t in ExhaustiveEnumeration(unused))
                    yield return used.Concat(t).ToArray();
            }
            //How to use
            //var allpattern = toolbox.ExhaustiveEnumeration(Enumerable.Range(1, N));
        }

        public bool[,] bitallsearch(int N)
        {
            bool[,] back = new bool[(int)Math.Pow(2, N), N];
            for (int i = 0; i < Math.Pow(2, N); i++)
            {
                for (int t = 0; t < N; t++)
                {
                    var k = (i >> t) & 1;
                    if (k == 1)
                    {
                        back[i, t] = true;
                    }
                }
            }
            return back;
        }

        public static int BS<T>(T[] A, T key)
            where T : IComparable
        {
            //このコード、定数倍が大変な事になってるので標準ライブラリを使いましょう(BinarySearch)
            int left = 0;
            int right = A.Length;
            int mid = 0;
            while (left < right)
            {
                mid = (left + right) / 2;
                if (A[mid].CompareTo(key) == 0)
                    return mid;
                else if (A[mid].CompareTo(key) > 0)
                    right = mid;
                else if (A[mid].CompareTo(key) < 0)
                    left = mid + 1;
            }
            return -1;
        }
        //単調増加なaの中で、v2"以上"の値を取る最小のインデックスを返す　存在しない場合。a.Count+1を返す
        public static int lower_bound<T>(T[] a, T v)
        {
            return lower_bound(a, v, Comparer<T>.Default);
        }

        public static int lower_bound<T>(T[] A, T key, Comparer<T> v)
        {
            int left = 0;
            int right = A.Length - 1;
            int mid = 0;
            var W = 0;
            while (left <= right)
            {
                mid = (left + right) / 2;
                W = v.Compare(A[mid], key);
                if (W == -1)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
            return left;
        }

        public long[] prime_factorize(long N)
        {
            long T = N;
            var back = new List<long>();
            for (long i = 2; i * i <= T; i++)
            {
                if (T % i != 0) continue;
                while (T % i == 0)
                {
                    back.Add(i);
                    T /= i;
                }
            }
            if (T != 1) back.Add(T);
            return back.ToArray();
        }

        public long[] One_dimensional_Coordinate_Compression(long[] A)
        {
            long[] back = new long[A.Length];
            var T = A.Distinct().ToList();
            T.Sort();
            for (int i = 0; i < A.Length; i++)
                back[i] = T.BinarySearch(A[i]);
            return back;
        }

        public void setYN(string A = "Yes", string B = "No")
        {
            Y = A;
            N = B;
        }

        public void YN(bool ans)
        {
            if (ans)
                Console.WriteLine(Y);
            else
                Console.WriteLine(N);
        }

        public string[] x_dekakou(int H, int W)
        {
            var s = new string[H + 2];
            for (int i = 0; i < W + 2; i++)
            {
                s[0] += "x";
                s[H + 1] += "x";
            }
            for (int i = 1; i < H + 1; i++)
            {
                //x場外　.白　#黒
                s[i] = "x" + Console.ReadLine().Replace(" ", "") + "x";
            }
            return s;
        }

        public List<List<char>> x_dekakou_char(int H, int W)
        {
            var grid = new List<List<char>>(H + 2);

            var border = new List<char>(W + 2);
            for (int i = 0; i < W + 2; i++)
                border.Add('x');
            grid.Add(new List<char>(border));

            for (int i = 0; i < H; i++)
            {
                var line = Console.ReadLine()?.Replace(" ", "") ?? string.Empty;
                var row = new List<char>(W + 2);
                row.Add('x');
                foreach (var c in line)
                    row.Add(c);
                row.Add('x');
                grid.Add(row);
            }

            grid.Add(new List<char>(border));
            return grid;
        }

        public List<List<int>> x_dekakou_string(int H, int W)
        {
            var back = new List<List<int>>();
            for (int i = 0; i < H + 2; i++)
                back.Add(Enumerable.Repeat<int>(-1, W + 2).ToList());
            for (int i = 0; i < W + 2; i++)
            {
                back[0][i] = -1;
                back[H + 1][i] = -1;
            }
            for (int i = 1; i <= H; i++)
            {
                back[i][0] = -1;
                back[i][W + 1] = -1;
                for (int t = 1; t <= W; t++)
                    back[i][t] = cin.intreed();
            }
            return back;
        }
        /// <summary>
        /// 配列の指定位置以降を反転する
        /// </summary>
        /// <param name="array">反転対象の配列</param>
        /// <param name="begin">反転開始位置（この位置以降が反転される）</param>
        private void Reverse<T>(T[] array, int begin) where T : IComparable<T>
        {
            // 反転する要素が2個未満の場合は何もしない
            if (array.Length - begin < 2) return;

            // 両端から中央に向かって要素を交換
            int left = begin;
            int right = array.Length - 1;
            while (left < right)
            {
                Swap(ref array[left], ref array[right]);
                left++;
                right--;
            }
        }

        /// <summary>
        /// 配列を辞書順で次の順列に変更する
        /// 全ての順列を列挙するには、事前に Array.Sort() でソートした配列を渡すこと
        /// </summary>
        /// <param name="array">順列を生成する配列（事前ソート必須）</param>
        /// <returns>次の順列が存在する場合true、最大順列の場合false</returns>
        public bool NextPermutation<T>(T[] array) where T : IComparable<T>
        {
            // 辞書順で次に大きい順列を生成

            // 1. 右端から降順でない位置を探す
            int pivotIndex = -1;
            for (int i = array.Length - 2; i >= 0; i--)
            {
                if (array[i].CompareTo(array[i + 1]) < 0) // 昇順ペア発見
                {
                    pivotIndex = i;
                    break;
                }
            }

            // 最大順列に到達している場合
            if (pivotIndex == -1) return false;

            // 2. pivotより大きい最右の要素と交換
            for (int j = array.Length - 1; j > pivotIndex; j--)
            {
                if (array[pivotIndex].CompareTo(array[j]) < 0)
                {
                    Swap(ref array[pivotIndex], ref array[j]);
                    break;
                }
            }

            // 3. pivot以降を昇順に並べ直し
            Reverse(array, pivotIndex + 1);
            return true;

            // how to use
            // do{}while(NextPermutation)
        }

        /// <summary>
        /// 回文判定のコア処理（配列版）
        /// </summary>
        private bool IsPalindromeCore<T>(T[] array, int left, int right) where T : IComparable<T>
        {
            while (left < right)
            {
                if (array[left].CompareTo(array[right]) != 0)
                    return false;
                left++;
                right--;
            }
            return true;
        }

        /// <summary>
        /// 回文判定のコア処理（文字列版）
        /// </summary>
        private bool IsPalindromeCore(string str, int left, int right)
        {
            while (left < right)
            {
                if (str[left] != str[right])
                    return false;
                left++;
                right--;
            }
            return true;
        }

        /// <summary>
        /// 配列全体が回文かどうかを判定
        /// </summary>
        public bool IsPalindrome<T>(T[] array) where T : IComparable<T>
        {
            return IsPalindromeCore(array, 0, array.Length - 1);
        }

        /// <summary>
        /// 文字列全体が回文かどうかを判定
        /// </summary>
        public bool IsPalindrome(string str)
        {
            return IsPalindromeCore(str, 0, str.Length - 1);
        }

        /// <summary>
        /// 指定範囲が回文かどうかを判定（配列版）
        /// </summary>
        public bool IsPalindrome<T>(T[] array, int start, int end) where T : IComparable<T>
        {
            return IsPalindromeCore(array, start, end);
        }

        /// <summary>
        /// 指定範囲が回文かどうかを判定（文字列版）
        /// </summary>
        public bool IsPalindrome(string str, int start, int end)
        {
            return IsPalindromeCore(str, start, end);
        }

        /// <summary>
        /// 指定長さの部分配列に回文が含まれるかを判定
        /// </summary>
        public bool HasPalindrome<T>(T[] array, int length) where T : IComparable<T>
        {
            for (int i = 0; i <= array.Length - length; i++)
            {
                if (IsPalindromeCore(array, i, i + length - 1))
                    return true;
            }
            return false;
        }

        /// <summary>
        /// 指定長さの部分文字列に回文が含まれるかを判定
        /// </summary>
        public bool HasPalindrome(string str, int length)
        {
            for (int i = 0; i <= str.Length - length; i++)
            {
                if (IsPalindromeCore(str, i, i + length - 1))
                    return true;
            }
            return false;
        }


        public long modpow(long x, long p, long mod = 1000000007)
        {
            long result = 1;
            x %= mod;
            while (p > 0)
            {
                if (p % 2 == 1)        // pが奇数の場合
                {
                    result = (result * x) % mod;
                }
                x = (x * x) % mod;      // xを二乗（これが繰り返し二乗）
                p /= 2;                 // pを半分にする
            }
            return result;
        }

        public void StartTimer()
        {
            startTime = DateTime.Now;
        }

        public void PrintElapsedTime(bool error_output = true)
        {
            //標準出力ではなくて標準エラー出力を使ってるのでatcoderのジャッジはこの出力を無視する　つまり消さなくてok　便利だね
            if (startTime.HasValue)
            {
                var elapsed = DateTime.Now - startTime.Value;
                if (error_output)
                    Console.Error.WriteLine($"Elapsed time: {elapsed.TotalMilliseconds} ms");
                else
                    Console.WriteLine($"Elapsed time: {elapsed.TotalMilliseconds} ms");


            }
            else
            {
                Console.Error.WriteLine("Timer was not started.");
            }
        }
    }

    internal class Priority_Queue
    {
        toolbox toolbox = new toolbox();
        public List<(long, long)> Queue { get; private set; }
        /// <summary>
        /// true==>大きいやつから出るよ　false==>小さいやつからでるよ
        /// </summary>
        public bool revase { get; set; }
        public Priority_Queue(bool cnt = true)
        {
            Queue = new List<(long, long)>();
            revase = cnt;
        }

        /// <summary>
        /// ヒープをO(N)で初期化するテク
        /// </summary>
        /// <param name="arr"></param>
        /// <param name="cnt"></param>
        public Priority_Queue(IEnumerable<(long, long)> arr, bool cnt = true)
        {
            revase = cnt;
            Queue = new List<(long, long)>();
            foreach (var item in arr)
            {
                var a = item.Item1;
                if (revase == false)
                    a *= -1;
                Queue.Add((a, item.Item2));
            }
            for (int i = Queue.Count / 2 - 1; i >= 0; i--)
            {
                int idx = i;
                while (true)
                {
                    int left = idx * 2 + 1;
                    if (left >= Queue.Count)
                        break;
                    int right = left + 1;
                    int child = left;
                    if (right < Queue.Count && Queue[left].Item1 < Queue[right].Item1)
                        child = right;
                    if (Queue[idx].Item1 < Queue[child].Item1)
                    {
                        var k = Queue[idx];
                        Queue[idx] = Queue[child];
                        Queue[child] = k;
                        idx = child;
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }

        public void Enqueue(long a, long b)
        {
            if (revase == false)
                a *= -1;
            int i = Queue.Count, t;
            Queue.Add((a, b));
            while (i != 0)
            {
                t = (i - 1) / 2;
                if (Queue[i].Item1 > Queue[t].Item1)
                {
                    var k = Queue[i];
                    Queue[i] = Queue[t];
                    Queue[t] = k;
                    i = t;
                }
                else
                {
                    break;
                }
            }
        }

        public (long, long) Dequeue()
        {
            int a = Queue.Count - 1;
            var back = Queue[0];
            Queue[0] = Queue[a];
            Queue.RemoveAt(a);
            for (int i = 0, j; (j = 2 * i + 1) < a;)
            {
                if (j != a - 1 && Queue[j].Item1 < Queue[j + 1].Item1)
                    j++;
                if (Queue[i].Item1 < Queue[j].Item1)
                {
                    var k = Queue[i];
                    Queue[i] = Queue[j];
                    Queue[j] = k;
                    i = j;
                }
                else
                {
                    break;
                }
            }
            if (revase == false)
                back.Item1 *= -1;
            return back;

        }

        public (long, long) GetPeek() => (revase ? Queue[0].Item1 : Queue[0].Item1 * -1, Queue[0].Item2);
    }

    internal class Generic_Priority_Queue<T>
    {
        toolbox toolbox = new toolbox();
        public List<(long, T)> Queue { get; private set; }
        /// <summary>
        /// true==>大きいやつから出るよ　false==>小さいやつからでるよ
        /// </summary>
        public bool revase { get; set; }
        public Generic_Priority_Queue(bool cnt = true)
        {
            Queue = new List<(long, T)>();
            revase = cnt;
        }

        public void Enqueue(long a, T b)
        {
            if (revase == false)
                a *= -1;
            int i = Queue.Count, t;
            Queue.Add((a, b));
            while (i != 0)
            {
                t = (i - 1) / 2;
                if (Queue[i].Item1 > Queue[t].Item1)
                {
                    var k = Queue[i];
                    Queue[i] = Queue[t];
                    Queue[t] = k;
                    i = t;
                }
                else
                {
                    break;
                }
            }
        }

        public (long, T) Dequeue()
        {
            int a = Queue.Count - 1;
            var back = Queue[0];
            Queue[0] = Queue[a];
            Queue.RemoveAt(a);
            for (int i = 0, j; (j = 2 * i + 1) < a;)
            {
                if (j != a - 1 && Queue[j].Item1 < Queue[j + 1].Item1)
                    j++;
                if (Queue[i].Item1 < Queue[j].Item1)
                {
                    var k = Queue[i];
                    Queue[i] = Queue[j];
                    Queue[j] = k;
                    i = j;
                }
                else
                {
                    break;
                }
            }
            if (revase == false)
                back.Item1 *= -1;
            return back;

        }

        public (long, T) get_first()
        {
            if (Queue.Count == 0)
                return (default(long), default(T));
            else
                return Queue[0];
        }
    }

}