using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Reflection;
using System.Text;
using System.Threading;
using System.Xml;
using static SolveApp.In;
using static SolveApp.Out;

namespace SolveApp
{
    class Program
    {
        static void Main(string[] args)
        {
            new arc171_b();
        }

        public class arc171_b
        {
            public arc171_b()
            {
                //input-------------
                (var A, var B, var C) = In.ReadTuple3<int>();
                //calc--------------
                Out.Write(Math.Min(B, A * C));

                return;
            }
        }

    }//

    //Common Class------------------------------------------------------------------------------------------------------------------------------------------

    public static class In
    {
        //1行=>1個の値取得
        public static T Read<T>() { var s = Console.ReadLine(); return (T)Convert.ChangeType(s, typeof(T)); }
        //1行=>n個の配列値取得
        public static T[] ReadAry<T>() { return Array.ConvertAll(Console.ReadLine().Split(' '), e => (T)Convert.ChangeType(e, typeof(T))); }
        //n行=>1個の値取得
        public static List<T> ReadMany<T>(long n) { var TT = new List<T>(); for (long i = 0; i < n; i++) TT.Add(Read<T>()); return TT; }
        //n行=>*個の配列値取得
        public static List<T[]> ReadManyAry<T>(long n) { var TT = new List<T[]>(); for (long i = 0; i < n; i++) TT.Add(ReadAry<T>()); return TT; }
        //1行=>"0101..."の文字列をint配列で取得
        public static int[] Read01() => Array.ConvertAll(Read<string>().ToCharArray(), e => (int)Convert.ChangeType(e.ToString(), typeof(int)));

        //1行=>n個のタプル取得
        public static (T, T) ReadTuple2<T>() { var c = ReadAry<T>(); return (c[0], c[1]); }
        public static (T, U) ReadTuple2<T, U>() { var c = ReadAry<string>(); return ((T)Convert.ChangeType(c[0], typeof(T)), (U)Convert.ChangeType(c[1], typeof(U))); }
        public static List<(T a, T b)> ReadTuple2Many<T>(long n) { var TT = new List<(T, T)>(); for (long i = 0; i < n; i++) TT.Add(ReadTuple2<T>()); return TT; }
        public static (T, T, T) ReadTuple3<T>() { var c = ReadAry<T>(); return (c[0], c[1], c[2]); }
        public static (T, U, V) ReadTuple3<T, U, V>() { var c = ReadAry<string>(); return ((T)Convert.ChangeType(c[0], typeof(T)), (U)Convert.ChangeType(c[1], typeof(U)), (V)Convert.ChangeType(c[2], typeof(V))); }
        public static (T, T, T, T) ReadTuple4<T>() { var c = ReadAry<T>(); return (c[0], c[1], c[2], c[3]); }
        public static (T, T, T, T, T) ReadTuple5<T>() { var c = ReadAry<T>(); return (c[0], c[1], c[2], c[3], c[4]); }
        public static (T, T, T, T, T, T) ReadTuple6<T>() { var c = ReadAry<T>(); return (c[0], c[1], c[2], c[3], c[4], c[5]); }
    }

    public static class Out
    {
        //1行出力
        public static void Write<T>(T item) => Console.WriteLine(item);
        //1行n個出力
        public static void WriteAry<T>(IEnumerable<T> items, string separetor = " ") => Write(string.Join(separetor, items));
        //n行1個出力
        public static void WriteMany<T>(IEnumerable<T> items, string separetor = " ") { foreach (var _i in items) Write(_i); }
        //n*m行1個出力
        public static void WriteMany<T>(T[,] items, string separetor = " ") { foreach (var _i in items) WriteAry(string.Join(separetor, _i)); }
        //n行m列出力
        public static void WriteManyAry<T>(IEnumerable<IEnumerable<T>> items, string separetor = " ") { foreach (var _i in items) WriteAry(_i, separetor); }
        public static void WriteManyAry<T>(IEnumerable<T[]> items, string separetor = " ") { foreach (var _i in items) WriteAry(_i, separetor); }
        public static void WriteManyAry<T>(T[,] items, string separetor = " ") { for (int i = 0; i < items.GetLength(0); i++) { var ary = new T[items.GetLength(1)]; for (int j = 0; j < items.GetLength(1); j++) { ary[j] = items[i, j]; } WriteAry(ary); } }
        //Y/N出力
        public static void WriteYN(bool result) { if (result) Write("Yes"); else Write("No"); }
    }

    public struct Con
    {
        public const long Mod = 998244353;
    }

    public enum Order
    {
        Ascending = 1,
        Descending = -1
    }


    /// <summary>
    /// はなちる氏のをほぼそのまま使ってます
    /// https://www.hanachiru-blog.com/entry/2020/06/19/141057
    /// LowerBoundを追加。TはIComparableに変更
    /// </summary>
    /// <typeparam name="T"></typeparam>

    public class SegmentTree<T>// where T : IComparable<T>
    {
        public int N { get; private set; }
        public int length { get; private set; }

        private T[] _tree;
        private readonly Func<T, T, T> _updateMethod;
        private readonly T _initValue;
        //private struct DefaultComparer<U> : IComparer<T> where U : IComparable<T> { public int Compare(T x, T y) => x.CompareTo(y); }

        /// <summary>
        /// セグメント木の初期化
        /// </summary>
        /// <param name="items">要素達</param>
        /// <param name="updateMethod">更新する方法</param>
        /// <param name="initValue">セグメント木のノードの初期値</param>
        public SegmentTree(IEnumerable<T> items, Func<T, T, T> updateMethod, T initValue)
        {
            T[] array = items.ToArray();
            _updateMethod = updateMethod;
            _initValue = initValue;
            length = array.Length;

            // セグ木の最下段は２の冪乗にする
            N = 1;
            while (N < length) N *= 2;

            _tree = Enumerable.Repeat(initValue, 2 * N - 1).ToArray();

            // 最下段に要素達を入れた後、下の段から更新していく
            for (int i = 0; i < length; i++) _tree[N + i - 1] = array[i];
            for (int i = N - 2; i >= 0; i--) _tree[i] = _updateMethod(_tree[2 * i + 1], _tree[2 * i + 2]);

        }

        /// <summary>
        /// 更新する
        /// </summary>
        /// <param name="i">更新したい値のインデックス</param>
        /// <param name="x">更新する値</param>
        public void Update(int i, T x)
        {
            // 更新したい要素のセグ木上でのインデックスを取得
            i = N + i - 1;

            // 値を更新した後に、どんどん親を更新していく
            _tree[i] = x;
            while (i > 0)
            {
                i = (i - 1) / 2;
                _tree[i] = _updateMethod(_tree[2 * i + 1], _tree[2 * i + 2]);
            }
        }

        /// <summary>
        /// 区間内の目的の値を取得する，要求区間[a, b)
        /// </summary>
        /// <param name="a">a以上の区間</param>
        /// <param name="b">b未満の区間</param>
        /// <returns></returns>
        public T Execute(int a, int b)
            => Execute(a, b, 0, 0, N);

        private T Execute(int a, int b, int k, int l, int r)
        {
            // 要求区間[a, b)に対して対象区間[l, r)を求める
            // 今いるノードのインデックスがk

            // 要求区間と対象区間が交わらない
            if (r <= a || b <= l) return _initValue;

            // 要求区間が対象区間を完全に被覆
            if (a <= l && r <= b) return _tree[k];

            // 要求区間が対象区間の一部を被覆しているので、子について探索を行う
            // 新しい対象区間は、現在の対象区間を半分に割ったもの
            var vl = Execute(a, b, 2 * k + 1, l, (l + r) / 2);
            var vr = Execute(a, b, 2 * k + 2, (l + r) / 2, r);
            return _updateMethod(vl, vr);
        }

        /// <summary>
        /// T[]が一様の単調増加のときのみ使用可
        /// [a,b)の範囲で値がv以下になる最大のindex:rを二分探索で求める
        /// </summary>
        /// <param name="v"></param>
        /// <param name="left"></param>
        /// <param name="right"></param>
        /// <returns></returns>
        public int LowerBound(T v, int left = 0, int right = int.MaxValue)
        {
            left = Math.Max(0, left);
            int l = left;
            int r = Math.Min(length, right);

            while (l < r)
            {
                int mid = l + (r - l) / 2;
                if (Comparer<T>.Default.Compare(Execute(left, mid + 1), v) <= 0)
                    l = mid + 1;
                else
                    r = mid;
            }

            return l;
        }
    }



    /// <summary>
    /// SCC : Strongly Connected Component 
    /// 任意の頂点v,uについて、v→uのパスとu→vのパスが存在する時、それらを同一の強連結成分という
    /// この同一の強連結成分のグループを取得する
    /// 自己辺,多重辺が含まれていてもOK
    /// 参考：https://qiita.com/AkariLuminous/items/a2c789cebdd098dcb503
    /// 入力にConnectedGlaphを使用
    /// </summary>
    public static class SCC
    {
        public static (int count, List<List<int>> groups) GetScc(int n, ConnectedGlaph cg)
        {
            var visited = new Stack<int>();
            int now_ord = 0, group_count = 0;
            var low = new int[n];
            var ids = new int[n];
            var ord_ = new int[n];

            //初期化
            for (int i = 0; i < n; i++)
                ord_[i] = -1;

            //まだ見ていない頂点を順番に見ていく
            for (int i = 0; i < n; i++)
                if (ord_[i] < 0)  
                    DFS_SCC(i);
            //カウント処理
            for (int i = 0; i < n; i++)
                ids[i] = group_count - 1 - ids[i];

            //出力
            var g = new List<List<int>>();
            for (int i = 0; i < group_count; i++)
                g.Add(new List<int>());
            for (int i = 0; i < n; i++)
                g[ids[i]].Add(i);

            return (group_count, g);

            void DFS_SCC(int v)
            {
                low[v] = ord_[v] = now_ord;
                now_ord++;
                visited.Push(v);

                if (cg[v] != null)
                {
                    // 行き先がある
                    foreach (var to in cg[v])
                    {
                        if (ord_[to] == -1)
                        {
                            DFS_SCC((int)to);
                            low[v] = Math.Min(low[v], low[to]);
                        }
                        else
                        {
                            low[v] = Math.Min(low[v], ord_[to]);
                        }
                    }
                }

                //帰りがけ
                if (low[v] == ord_[v])
                {
                    while (true)
                    {
                        int u = visited.Pop();
                        ord_[u] = n;
                        ids[u] = group_count;
                        if (u == v) break;
                    }
                    group_count++;
                }
            }
        }
    }



    /// <summary>
    /// ダイクストラ法
    /// 各ノードへの最短経路を、始点の周辺から１個所ずつ確定し、徐々に範囲を広げていく方法
    /// グラフの重みマイナスがある場合は不可
    /// PriorityQueue、ConnectedGlaphAndValueを使用する
    /// </summary>
    public static class AlgoDijkstra
    {
        /// <summary>
        /// ダイクストラ法処理メイン
        /// i→jの重みgは配列pの[i,j]に書かれていることとする
        /// </summary>
        public static long[] GetEachWeight(long[,] p, int _start = 0, Order order = Order.Descending)
        {
            int start = _start;
            int size = p.GetLength(0);

            //判明したフラグ
            var seen = new bool[size];
            seen[start] = true;
            //判明した最小重み
            var pw = new long[size];
            pw[start] = 0;
            //判明数
            int cnt = 0;

            //優先度つきキューで近い場所から順に探す
            var pq = new PriorityQueue<(long p, int idx)>(Compare, order);
            for (int i = 0; i < size; i++)
                pq.Push((p[start, i], i));

            while (pq.Count > 0)
            {
                var v = pq.Pop();
                if (seen[v.idx]) continue; //既知の頂点は飛ばす

                seen[v.idx] = true;
                pw[v.idx] = v.p;
                cnt++;

                if (cnt == size) break;

                for (int i = 0; i < size; i++)
                {
                    if (seen[i]) continue; //既知の頂点は飛ばす
                    pq.Push((v.p + p[v.idx, i], i));
                }
            }
            return pw;
        }

        /// <summary>
        /// ダイクストラ法処理メイン
        /// p:(index,i,j,p) : index番目の辺が、i→jの重みg　とする 　※有向グラフの場合はisDirection=falseにすること
        /// order:最小or最大
        /// </summary>
        public static long[] GetEachWeight(List<(int index, int i, int j, long g)> p, int n, int _start = 0, bool isDirection = true, Order order = Order.Descending)
        {
            int start = _start;
            int size = n;
            int rowcount = p.Count;

            //判明したフラグ
            var seen = new bool[size];
            seen[start] = true;
            //判明した最小重み
            var pw = new long[size];
            pw[start] = 0;
            //判明数
            int cnt = 0;

            //繋がっているかどうかを処理する

            var ab = new long[rowcount][];
            for (int i = 0; i < rowcount; i++)
                ab[i] = new long[] { p[i].i, p[i].j, p[i].g, p[i].index };
            var con = new ConnectedGlaphAndValue(ab, isDirection);

            //優先度つきキューで近い場所から順に探す
            var pq = new PriorityQueue<(long p, int rowindex, int idx)>(Compare, order);
            for (int c = 0; c < rowcount; c++)
            {
                if (p[c].i == start)
                    pq.Push((p[c].g, p[c].index, p[c].j));
                if (isDirection && p[c].j == start)
                    pq.Push((p[c].g, p[c].index, p[c].i));
            }

            while (pq.Count > 0)
            {
                var v = pq.Pop();
                if (seen[v.idx]) continue; //既知の頂点は飛ばす

                seen[v.idx] = true;
                pw[v.idx] = v.p;

                cnt++;

                //
                //v.idxが接続している直前の辺は、v.rowindexで取得できる
                //

                if (cnt == size) break;

                foreach (var next in con[v.idx])
                {
                    if (seen[next.Key]) continue; //既知の頂点は飛ばす
                    pq.Push((v.p + next.Value[0], (int)next.Value[1], (int)next.Key));
                }
            }
            return pw;
        }

        //goalまでの距離だけ知りたいVer
        public static long GetSingle(long[,] p, int _start = 0, int _goal = -1, Order order = Order.Descending)
        {
            int start = _start;
            int goal = _goal == -1 ? p.GetLength(0) : _goal;
            int size = p.GetLength(0);

            //判明したフラグ
            var seen = new bool[size];
            //判明した最小重み
            var pw = new long[size];
            seen[start] = true;
            pw[start] = 0;

            //優先度つきキューで近い場所から順に探す
            var pq = new PriorityQueue<(long p, int idx)>(Compare, order);
            for (int i = 0; i < size; i++)
                pq.Push((p[start, i], i));

            while (pq.Count > 0)
            {
                var v = pq.Pop();
                if (seen[v.idx]) continue; //既知の頂点は飛ばす

                seen[v.idx] = true;
                pw[v.idx] = v.p;

                if (v.idx == goal) break; //向かいたい頂点の距離が判明したので終了する

                for (int i = 0; i < size; i++)
                {
                    if (seen[i]) continue; //既知の頂点は飛ばす
                    pq.Push((v.p + p[v.idx, i], i));
                }
            }
            return pw[goal];
        }

        private static int Compare((long p, int idx) x, (long p, int idx) y)
        {
            return x.p > y.p ? 1 : -1;
        }
        static int Compare((long p, int rowindex, int idx) x, (long p, int rowindex, int idx) y)
        {
            return x.p > y.p ? 1 : -1;
        }
    }



    /// <summary>
    /// 優先度付き待ち行列
    /// </summary>
    /// <typeparam name="T">要素の型</typeparam>
    public class PriorityQueue<T> : IEnumerable<T> //where T : IComparable<T>
    {
        #region フィールド

        private List<T> buffer;
        private readonly Comparison<T> cmp;
        private readonly int reverseFactor;

        #endregion
        #region 初期化

        //基本
        public PriorityQueue()
        {
            cmp = Comparer<T>.Default.Compare;
            buffer = new List<T>();
            reverseFactor = (int)Order.Descending;
        }

        //容量決めての初期化(気持ち早くなる), ソート順を決めての初期化
        public PriorityQueue(int capacity = -1, Order _reverseFactor = Order.Descending)
        {
            cmp = Comparer<T>.Default.Compare;
            buffer = new List<T>(capacity);
            reverseFactor = (int)_reverseFactor;
        }

        //初期配列をそのまま入れる初期化, ソート順を決めての初期化
        public PriorityQueue(IEnumerable<T> initBuffer, Order _reverseFactor = Order.Descending)
        {
            cmp = Comparer<T>.Default.Compare;
            buffer = new List<T>(initBuffer.Count());
            reverseFactor = (int)_reverseFactor;

            foreach (var ib in initBuffer)
                PushHeap(ib);
        }

        //比較ルールを決めての初期化1
        public PriorityQueue(Comparison<T> comparison, Order _reverseFactor = Order.Descending)
        {
            cmp = comparison;
            buffer = new List<T>();
            reverseFactor = (int)_reverseFactor;
        }

        //比較ルールを決めての初期化2
        public PriorityQueue(IComparer<T> comparer, Order _reverseFactor = Order.Descending)
        {
            cmp = comparer.Compare;
            buffer = new List<T>();
            reverseFactor = (int)_reverseFactor;
        }

        #endregion
        #region ヒープ操作

        /// <summary>
        /// ヒープ化されている配列リストに新しい要素を追加する。
        /// </summary>
        /// <param name="buffer">対象の配列リスト</param>
        private void PushHeap(T elem)
        {
            int n = buffer.Count;
            buffer.Add(elem);

            while (n != 0)
            {
                int i = (n - 1) / 2;
                if (Compare(buffer[n], buffer[i]) < 0)
                {
                    var tmp = buffer[i];
                    buffer[i] = buffer[n];
                    buffer[n] = tmp;
                }
                n = i;
            }
        }

        /// <summary>
        /// ヒープから最大値を削除し、その値を返す。O(logN)
        /// </summary>
        /// <returns>優先度付きキューから削除された要素</returns>
        public T PopHeap()
        {
            var ret = buffer[0];
            var pos = 0;

            int cnt = buffer.Count - 1;
            var x = buffer[cnt];

            while (pos * 2 + 1 < cnt)
            {
                var lch = pos * 2 + 1;
                var rch = pos * 2 + 2;
                if (rch < cnt && Compare(buffer[rch], buffer[lch]) < 0) lch = rch;
                if (Compare(buffer[lch], x) >= 0)
                    break;
                buffer[pos] = buffer[lch];
                pos = lch;
            }

            buffer[pos] = x;
            buffer.RemoveAt(cnt);
            return ret;
        }


        #endregion
        #region 要素の挿入・削除

        /// <summary>
        /// 要素のプッシュ。
        /// </summary>
        /// <param name="elem">挿入したい要素</param>
        public void Push(T elem) => PushHeap(elem);
        public void Enqueue(T elem) => PushHeap(elem);

        /// <summary>
        /// 要素を1つポップ。
        /// </remarks>
        public T Pop() => PopHeap();
        public T Dequeue() => PopHeap();

        /// <summary>
        /// 先頭要素の読み出し。
        /// </summary>
        public T Peek() => buffer[0];

        /// <summary>
        /// カウント
        /// </summary>
        public int Count { get => buffer.Count; }

        public int Compare(T a, T b) => reverseFactor * cmp(a, b);

        public IEnumerator<T> GetEnumerator()
        {
            foreach (var t in buffer)
                yield return Pop();
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();

        #endregion
    }


    /// <summary>
    /// Union-Find atcoder::dsuを参考に高速化済(ソースは別言語のサンプルをもとに作成)
    /// 2次元対応追加
    /// </summary>
    public class UnionFind
    {
        int[] par; //親がいるとき、親のindex。 ／　親がいない(自分が一番上)のとき、子の要素の数*(-1)
        int h, w; //二次元Union-Find用 初期化時にセット必須

        // インスタンスでサイズセットと初期化
        public UnionFind(int h, int w) : this(h * w)
        {
            this.h = h;
            this.w = w;
        }
        public UnionFind(int n)
        {
            par = new int[n];
            for (int i = 0; i < n; i++)
                par[i] = -1;
        }
        // 別のufを使いまわしたい時専用
        public UnionFind(UnionFind un)
        {
            par = new int[un.par.Length];
            Array.Copy(un.par, par, un.par.Length);
            this.h = un.h;
            this.w = un.w;
        }

        // 親を探す
        public int Find(int i, int j) => Find(i * w + j);
        public int Find(int x)
        {
            if (par[x] < 0) return x;
            return par[x] = Find(par[x]);
        }

        // 接続する(親が一致しない時)
        public void Unite(int xi, int xj, int yi, int yj) => Unite(xi * w + xj, yi * w + yj);
        public void Unite(int x, int y)
        {
            x = Find(x);
            y = Find(y);
            if (x == y) return;
            if (-par[x] < -par[y]) (x, y) = (y, x);

            //ツリー情報更新
            par[x] += par[y];
            par[y] = x;
        }

        // 同じかどうかチェック
        public bool IsSame(int xi, int xj, int yi, int yj) => Find(xi, xj) == Find(yi, yj);
        public bool IsSame(int x, int y) => Find(x) == Find(y);


        public int Size(int xi, int xj) => -par[Find(xi, xj)];
        public int Size(int x) => -par[Find(x)];
    }


    /// <summary>
    /// 連結グラフの問題用
    /// U,V,(params)
    /// isDirection:有向グラフ:false, 無向:true
    /// </summary>
    public class ConnectedGlaph : IEnumerable<(long u, long v)>
    {
        public Dictionary<long, List<long>> _sortedGlaph;
        private List<(long u, long v)> _Array; //ToArrayやCountなどが毎回O(グラフの数)だけかかってしまうため、1回やったときに作っておく

        //入力から直接取り込むVer
        public ConnectedGlaph(int rowcnt, bool isDirection = false, bool isMinusOne = false)
        {
            int tc = rowcnt;
            int minus = isMinusOne ? 1 : 0;
            _sortedGlaph = new Dictionary<long, List<long>>();

            for (int r = 0; r < tc; r++)
            {
                long[] t = In.ReadAry<long>();

                if (_sortedGlaph.TryGetValue(t[0] - minus, out var cols))
                    cols.Add(t[1] - minus);
                else
                    _sortedGlaph[t[0] - minus] = new List<long>() { t[1] - minus };

                if (isDirection) //反対方向
                {
                    if (_sortedGlaph.TryGetValue(t[1] - minus, out var colsx))
                        colsx.Add(t[0] - minus);
                    else
                        _sortedGlaph[t[1] - minus] = new List<long>() { t[0] - minus };
                }
            }

            foreach (var v in _sortedGlaph.Values)
                v.Sort();
        }

        //配列から取り込むVer
        public ConnectedGlaph(long[][] t, bool isDirection = false, bool isMinusOne = false)
        {
            int tc = t.Count();
            int minus = isMinusOne ? 1 : 0;
            _sortedGlaph = new Dictionary<long, List<long>>();

            for (int i = 0; i < tc; i++)
            {
                if (_sortedGlaph.TryGetValue(t[i][0] - minus, out var cols))
                    cols.Add(t[i][1] - minus);
                else
                    _sortedGlaph[t[i][0] - minus] = new List<long>() { t[i][1] - minus };
            }

            if (isDirection) //反対方向
            {
                for (int i = 0; i < tc; i++)
                {
                    if (_sortedGlaph.TryGetValue(t[i][1] - minus, out var cols))
                        cols.Add(t[i][0] - minus);
                    else
                        _sortedGlaph[t[i][1] - minus] = new List<long>() { t[i][0] - minus };
                }
            }

            foreach (var v in _sortedGlaph.Values)
                v.Sort();
        }
        public ConnectedGlaph(int[][] t, bool isDirection = false, bool isMinusOne = false) : this(t.Select(p => { return Array.ConvertAll(p, e => (long)Convert.ChangeType(e, typeof(long))); }).ToArray(), isDirection, isMinusOne)
        {
        }
        public ConnectedGlaph(List<int[]> t, bool isDirection = false, bool isMinusOne = false) : this(t.Select(p => { return Array.ConvertAll(p, e => (long)Convert.ChangeType(e, typeof(long))); }).ToArray(), isDirection, isMinusOne)
        {
        }
        public ConnectedGlaph(List<long[]> t, bool isDirection = false, bool isMinusOne = false) : this(t.Select(p => { return Array.ConvertAll(p, e => (long)Convert.ChangeType(e, typeof(long))); }).ToArray(), isDirection, isMinusOne)
        {
        }

        //存在する[i,*]の*のコレクションを返す
        public List<long> this[long i]
        {
            get
            {
                if (_sortedGlaph.TryGetValue(i, out var cols))
                    return cols;
                else
                    return null;
            }
        }

        //そのグラフがあるかどうか。
        public bool IsExist(long i, long j)
        {
            if (!_sortedGlaph.ContainsKey(i)) return false;
            int idx = GetIndex(i, j, 0, _sortedGlaph[i].Count());
            if (idx == -1) return false;
            return true;
        }

        private int GetIndex(long row, long i, int st = 0, int ed = -1)
        {
            if (ed - st <= 0)//最後1回
                return _sortedGlaph[row][st] == i ? st : -1;

            int half = st + (ed - st) / 2;

            if (_sortedGlaph[row][half] > i)
                return GetIndex(row, st, half);
            else if (_sortedGlaph[row][half] < i)
                return GetIndex(row, half + 1, ed);
            else
                return half;
        }

        //以下、IEnumerable<(u,v)>として操作したいときの処理
        public int Count()
        {
            TryMakeArray();
            return _Array.Count();
        }

        IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
        public IEnumerator<(long u, long v)> GetEnumerator()
        {
            TryMakeArray();
            return new Enumerator(_Array);
        }

        private void TryMakeArray()
        {
            if (_Array == null)
            {
                _Array = new List<(long u, long v)>();
                foreach (var d in _sortedGlaph)
                    foreach (var e in d.Value)
                        _Array.Add((d.Key, e));
            }
        }

        // IEnumeratorを実装する
        public class Enumerator : IEnumerator<(long u, long v)>
        {
            private readonly List<(long u, long v)> list;
            private int index;

            internal Enumerator(List<(long u, long v)> list)
            {
                this.list = list;
                index = -1;
            }

            public bool MoveNext()
            {
                index++;
                return (uint)index < (uint)list.Count;
            }

            public void Reset()
            {
                index = -1;
            }

            public (long u, long v) Current => list[index];
            object IEnumerator.Current => Current;

            public void Dispose() { }
        }
    }

    /// <summary>
    /// 連結グラフの問題用
    /// U,V,(params)
    /// isDirection:有向グラフ:false, 無向:true
    /// </summary>
    public class ConnectedGlaphAndValue : IEnumerable<(long u, long v, long[] p)>
    {
        private Dictionary<long, List<(long Key, long[] Value)>> _sortedGlaph;
        private Dictionary<long, (int left, int right)> _knowIndex; //特定のiから始まる[i,*]のデータが多いときで、[i,*]検索するときは、何度も行うことになるので効率化のためここに覚えておく。

        //入力から直接取り込むVer
        public ConnectedGlaphAndValue(int rowcnt, bool isDirection = false, bool isMinusOne = false)
        {
            int tc = rowcnt;
            int minus = isMinusOne ? 1 : 0;
            _sortedGlaph = new Dictionary<long, List<(long Key, long[] Value)>>();
            _knowIndex = new Dictionary<long, (int left, int right)>();

            for (int r = 0; r < tc; r++)
            {
                long[] t = In.ReadAry<long>();

                if (_sortedGlaph.TryGetValue(t[0] - minus, out var cols))
                    cols.Add((t[1] - minus, t.Skip(2).ToArray()));
                else
                    _sortedGlaph[t[0] - minus] = new List<(long, long[])>() { (t[1] - minus, t.Skip(2).ToArray()) };

                if (isDirection) //反対方向
                {
                    if (_sortedGlaph.TryGetValue(t[1] - minus, out var colsx))
                        colsx.Add((t[0] - minus, t.Skip(2).ToArray()));
                    else
                        _sortedGlaph[t[1] - minus] = new List<(long, long[])>() { (t[0] - minus, t.Skip(2).ToArray()) };
                }
            }

            foreach (var v in _sortedGlaph.Values)
                v.Sort();
        }

        public ConnectedGlaphAndValue(long[][] t, bool isDirection = false, bool isMinusOne = false)
        {
            int tc = t.Count();
            int minus = isMinusOne ? 1 : 0;
            _sortedGlaph = new Dictionary<long, List<(long Key, long[] Value)>>();
            _knowIndex = new Dictionary<long, (int left, int right)>();

            for (int i = 0; i < tc; i++)
            {
                if (_sortedGlaph.TryGetValue(t[i][0] - minus, out var cols))
                    cols.Add((t[i][1] - minus, t[i].Skip(2).ToArray()));
                else
                    _sortedGlaph[t[i][0] - minus] = new List<(long, long[])>() { (t[i][1] - minus, t[i].Skip(2).ToArray()) };
            }

            if (isDirection) //反対方向
            {
                for (int i = 0; i < tc; i++)
                {
                    if (_sortedGlaph.TryGetValue(t[i][1] - minus, out var cols))
                        cols.Add((t[i][0] - minus, t[i].Skip(2).ToArray()));
                    else
                        _sortedGlaph[t[i][1] - minus] = new List<(long, long[])>() { (t[i][0] - minus, t[i].Skip(2).ToArray()) };
                }
            }

            foreach (var key in _sortedGlaph.Keys.ToArray())
                _sortedGlaph[key] = _sortedGlaph[key].OrderBy(p => p.Key).ToList();
        }
        public ConnectedGlaphAndValue(int[][] t, bool isDirection = false, bool isMinusOne = false) : this(t.Select(p => { return Array.ConvertAll(p, e => (long)Convert.ChangeType(e, typeof(long))); }).ToArray(), isDirection, isMinusOne)
        {
        }
        public ConnectedGlaphAndValue(List<int[]> t, bool isDirection = false, bool isMinusOne = false) : this(t.Select(p => { return Array.ConvertAll(p, e => (long)Convert.ChangeType(e, typeof(long))); }).ToArray(), isDirection, isMinusOne)
        {
        }
        public ConnectedGlaphAndValue(List<long[]> t, bool isDirection = false, bool isMinusOne = false) : this(t.Select(p => { return Array.ConvertAll(p, e => (long)Convert.ChangeType(e, typeof(long))); }).ToArray(), isDirection, isMinusOne)
        {
        }

        //存在する[i,*]の*のコレクションを返す
        public IEnumerable<(long Key, long[] Value)> this[long i]
        {
            get
            {
                if (!_sortedGlaph.ContainsKey(i)) yield break;
                foreach (var e in _sortedGlaph[i])
                    yield return e;
            }
        }

        //そのグラフがあるかどうか。あればparams,なければnullを返す
        public IEnumerable<long> this[long i, long j]
        {
            get
            {
                if (!_sortedGlaph.ContainsKey(i)) return null;
                int idx = GetIndex(i, j, 0, _sortedGlaph[i].Count());
                if (idx == -1) return null;
                return _sortedGlaph[i][idx].Value;
            }
        }

        //そのグラフがあるかどうか。
        public bool IsExist(long i, long j)
        {
            if (!_sortedGlaph.ContainsKey(i)) return false;
            int idx = GetIndex(i, j, 0, _sortedGlaph[i].Count());
            if (idx == -1) return false;
            return true;
        }

        private int GetIndex(long row, long i, int st = 0, int ed = -1)
        {
            if (ed - st <= 0)//最後1回
                return _sortedGlaph[row][st].Key == i ? st : -1;

            int half = st + (ed - st) / 2;

            if (_sortedGlaph[row][half].Key > i)
                return GetIndex(row, st, half);
            else if (_sortedGlaph[row][half].Key < i)
                return GetIndex(row, half + 1, ed);
            else
                return half;
        }

        public IEnumerator<(long u, long v, long[] p)> GetEnumerator()
        {
            foreach (var d in _sortedGlaph)
                foreach (var e in d.Value)
                    yield return (d.Key, e.Key, e.Value);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            throw new NotImplementedException();
        }
    }
}