#include"bits/stdc++.h"
using namespace std;
template<typename T_container,typename T=typename enable_if<!is_same<T_container,string>::value,typename T_container::value_type>::type>istream&operator>>(istream&is,T_container&v){for(T&x:v)is>>x;return is;}
ostream&operator<<(ostream&os,__int128 const&value){
    static char buffer[64];
    int index=0;
    __uint128_t T=(value<0)?(-(value+1))+__uint128_t(1):value;
    if(value<0)os<<'-';
    else if(T==0)return os<<'0';
    for(;T>0;++index)buffer[index]=static_cast<char>('0'+(T%10)),T/=10;
    while(index>0)os<<buffer[--index];
    return os;
}
istream&operator>>(istream &is,__int128&T){
    static char buffer[64];
    is >> buffer;
    size_t len = strlen(buffer), index = 0;
    T = 0;
    int mul = 1;
    if (buffer[index] == '-')
        ++index, mul=-mul;
    for (; index < len; ++index)
        T = T * 10 + static_cast<int>(buffer[index] - '0');
    T *= mul;
    return is;
}
namespace FastIO{
namespace Internal{
template<typename T>struct internal_get_unsigned{typedef typename make_unsigned<T>::type type;};
template<>struct internal_get_unsigned<__int128>{typedef __uint128_t type;};
template<>struct internal_get_unsigned<__uint128_t>{typedef __uint128_t type;};
template<class T>struct is_int{static constexpr bool value=is_integral<T>::value;};
template<>struct is_int<__int128_t>{static constexpr bool value=1;};
template<>struct is_int<__uint128_t>{static constexpr bool value=1;};
template<class T>struct is_char{static constexpr bool value=is_same<T,char>::value;};
template<class T>struct is_bool{static constexpr bool value=is_same<T,bool>::value;};
template<class T>struct is_string{static constexpr bool value=is_same<T,string>::value||is_same<T,const char*>::value||is_same<T,char*>::value||is_same<decay_t<T>,char*>::value;};
template<class T,class D=void>struct is_custom{static constexpr bool value=0;};
template<class T>struct is_custom<T,void_t<typename T::internal_value_type>>{static constexpr bool value=1;};
template<class T>
struct is_default{
    static constexpr bool value = is_char<T>::value || is_bool<T>::value ||
                                  is_string<T>::value ||
                                  is_int<T>::value;
};

template <class T, class D = void>
struct is_iterable {
    static constexpr bool value = false;
};

template <class T>
struct is_iterable <
T, typename std::void_t<decltype(std::begin(std::declval<T>())) >> {
    static constexpr bool value = true;
};

template <class T, class D = void, class E = void>
struct is_applyable {
    static constexpr bool value = false;
};

template <class T>
struct is_applyable<T, std::void_t<typename std::tuple_size<T>::type>,
       std::void_t<decltype(std::get<0>(std::declval<T>()))>> {
           static constexpr bool value = true;
       };
};

struct IOPre {
    static constexpr int TEN = 10, SZ = TEN * TEN * TEN * TEN;
    std::array<char, 4 * SZ> num;
    constexpr IOPre() : num{} {
        for (int i = 0; i < SZ; i++) {
            int n = i;

            for (int j = 3; j >= 0; j--) {
                num[i * 4 + j] = static_cast<char>(n % TEN + '0');
                n /= TEN;
            }
        }
    }
};

template<const bool SAFETY_CHECKS>
struct IO {


#if !HAVE_DECL_FREAD_UNLOCKED
#define fread_unlocked fread
#endif
#if !HAVE_DECL_FWRITE_UNLOCKED
#define fwrite_unlocked fwrite
#endif

    static constexpr int BUFFER_SIZE = 1 << 17, LEN = 64, TEN = 10, HUNDRED = TEN * TEN,
                         THOUSAND = HUNDRED * TEN, TENTHOUSAND = THOUSAND * TEN,
                         MAGIC_MULTIPLY = 205, MAGIC_SHIFT = 11, MASK = 15,
                         TWELVE = 32, SIXTEEN = 36, INTEGER_WIDTH = 64;
    static constexpr IOPre io_pre = {};


    std::array<char, BUFFER_SIZE> input_buffer, output_buffer;
    int input_start_ptr, input_end_ptr, output_end_ptr;
    bool end_of_file;

    FILE *read_fptr, *write_fptr;

    IO(FILE *read_fp, FILE *write_fp): read_fptr(read_fp), write_fptr(write_fp), input_buffer{}, output_buffer{},
        input_start_ptr{}, input_end_ptr{}, output_end_ptr{}, end_of_file(false) {}
    IO(const IO &) = delete;
    IO(IO &&) = delete;
    IO &operator = (const IO &) = delete;
    IO &operator = (const IO &&) = delete;

    ~IO() {
        flush();
    }

    template <class T>
    static constexpr bool needs_newline = (Internal::is_iterable<T>::value ||
                                           Internal::is_applyable<T>::value) &&
                                          (!Internal::is_default<T>::value);

    template <typename T, typename U>
    struct any_needs_newline {
        static constexpr bool value = false;
    };
    template <typename T>
    struct any_needs_newline<T, std::index_sequence<>> {
        static constexpr bool value = false;
    };
    template <typename T, std::size_t I, std::size_t... Is>
    struct any_needs_newline<T, std::index_sequence<I, Is...>> {
        static constexpr bool value =
            needs_newline<decltype(std::get<I>(std::declval<T>()))> ||
            any_needs_newline<T, std::index_sequence<Is...>>::value;
    };


    inline bool
    reload() { // Reloads without already read checks -- add read check for eof in interactive problems?.
        if constexpr(SAFETY_CHECKS) {
            assert(input_end_ptr >= input_start_ptr);
        }


        if (input_start_ptr > (BUFFER_SIZE >> 1))
            [[unlikely]] {
            memmove(std::begin(input_buffer), std::begin(input_buffer) + input_start_ptr, input_end_ptr - input_start_ptr);
            input_end_ptr -= input_start_ptr;
            input_start_ptr = 0;
        }

        if (end_of_file)
            [[unlikely]]
            return false;
        else if (input_end_ptr == BUFFER_SIZE)
            [[unlikely]]
            return true;

        size_t read_length = fread_unlocked(std::begin(input_buffer) + input_end_ptr, sizeof(char),
                                            BUFFER_SIZE - input_end_ptr, read_fptr);

        if (read_length == 0) {
            end_of_file = true;
            input_buffer[input_end_ptr] = '\0';
            read_length = 1;
        }

        input_end_ptr += read_length;
        return true;
    }

    inline bool read_char(char &c) {
        if (input_start_ptr == input_end_ptr)
            [[unlikely]] {
            if (!reload())
                return false;
        }
        c = input_buffer[input_start_ptr++];
        return true;
    }

    inline bool read_string(std::string &s) {
        while (true) {
            while (input_start_ptr < input_end_ptr && input_buffer[input_start_ptr] <= ' ')
                ++input_start_ptr;

            if (input_start_ptr < input_end_ptr)
                break;

            if (!reload())
                return false;
        }

        s.clear();
        char x;

        while (true) {
            if (!read_char(x) || x <= ' ') // read_char will always be true?
                break;

            s += x;
        }

        return !s.empty();
    }

    template <class T>
    inline typename std::enable_if<std::is_floating_point<T>::value, bool>::type read_float(
        T &x) { // No custom implementation -- maybe even slower.
        std::string s;

        if (!read_string(s))
            return false;

        x = std::stold(s);
        return true;
    }

    template <class T>inline typename enable_if<Internal::is_int<T>::value, bool>::type read_int(T&x){
        using U = typename Internal::internal_get_unsigned<T>::type;
        while(1){
            while(input_start_ptr<input_end_ptr&&input_buffer[input_start_ptr]<'-')++input_start_ptr;
            if(input_start_ptr<input_end_ptr)break;
            if(!reload())return false;
        }
        if(input_start_ptr+INTEGER_WIDTH>input_end_ptr)reload();
        if(input_start_ptr==input_end_ptr)return false;
        bool minus=0;
        if(input_buffer[input_start_ptr] == '-')minus=1,++input_start_ptr;
        x=0;
        char c;
        while(input_start_ptr < input_end_ptr) {
            c=input_buffer[input_start_ptr];
            if(c<'0'||c>'9')break;
            ++input_start_ptr;
            x = x * TEN + (c & MASK);
        }

        if (minus)
            x = -x;

        return true;
    }
    inline void flush() {
        fwrite_unlocked(std::begin(output_buffer), sizeof(char), output_end_ptr, write_fptr);
        output_end_ptr = 0;
    }

    template <typename T>
    IO &operator >> (T &x) {
        static_assert(Internal::is_custom<T>::value or Internal::is_default<T>::value or
                      Internal::is_iterable<T>::value or Internal::is_applyable<T>::value or is_floating_point<T>::value);
        static_assert(!Internal::is_bool<T>::value);
        bool was_read = false;

        if constexpr(Internal::is_custom<T>::value){
            typename T::internal_value_type y;
            was_read=read_int(y);
            x=y;
        }
        else if constexpr(Internal::is_default<T>::value){
            if constexpr(Internal::is_string<T>::value)was_read=read_string(x);
            else if constexpr(Internal::is_char<T>::value)was_read=read_char(x);
            else if constexpr(Internal::is_int<T>::value)was_read=read_int(x);
        } else if constexpr(is_floating_point<T>::value) {
            was_read = read_float(x);
        } else if constexpr(Internal::is_iterable<T>::value) {
            for (auto &y : x)
                operator>>(y);
        } else if constexpr(Internal::is_applyable<T>::value) {
            std::apply([this](auto & ... y) {
                ((this->operator>>(y)), ...);
            }, x);
        }

        if constexpr(SAFETY_CHECKS and (Internal::is_custom<T>::value or Internal::is_default<T>::value or
                                        is_floating_point<T>::value)) {
            assert(was_read);
        }

        return *this;
    }

    inline void write_char(char c) {
        if (output_end_ptr == BUFFER_SIZE)
            [[unlikely]] flush();

        output_buffer[output_end_ptr++] = c;
    }

    inline void write_bool(bool b) {
        if (output_end_ptr == BUFFER_SIZE)
            [[unlikely]] flush();

        output_buffer[output_end_ptr++] = b ? '1' : '0';
    }

    inline void write_string(const std::string &s) {
        for (const auto &x : s)
            write_char(x);
    }

    inline void write_string(const char *s) {
        while (*s)
            write_char(*s++);
    }

    inline void write_string(char *s) {
        while (*s)
            write_char(*s++);
    }

    template <typename T>
    inline typename std::enable_if<Internal::is_int<T>::value, void>::type write_int(const T &y) {
        using U = typename Internal::internal_get_unsigned<T>::type;

        if (output_end_ptr > BUFFER_SIZE - INTEGER_WIDTH)
            flush();

        if (!y) {
            output_buffer[output_end_ptr++] = '0';
            return;
        }

        U x = y;

        if (y < 0)
            output_buffer[output_end_ptr++] = '-', x = -y;

        int i = TWELVE;
        static std::array<char, SIXTEEN> buf{};

        while (x >= TENTHOUSAND) {
            memcpy(std::begin(buf) + i,
                   std::begin(io_pre.num) + (x % TENTHOUSAND) * 4, 4);
            x /= TENTHOUSAND;
            i -= 4;
        }

        if (x < HUNDRED) {
            if (x < TEN) {
                output_buffer[output_end_ptr++] = static_cast<char>('0' + x);
            } else {
                std::uint32_t q =
                    (static_cast<std::uint32_t>(x) * MAGIC_MULTIPLY) >>
                    MAGIC_SHIFT;
                std::uint32_t r = static_cast<std::uint32_t>(x) - q * TEN;
                output_buffer[output_end_ptr] = static_cast<char>('0' + q);
                output_buffer[output_end_ptr + 1] =
                    static_cast<char>('0' + r);
                output_end_ptr += 2;
            }
        } else {
            if (x < THOUSAND) {
                memcpy(std::begin(output_buffer) + output_end_ptr,
                       std::begin(io_pre.num) + (x << 2) + 1, 3),
                           output_end_ptr += 3;
            } else {
                memcpy(std::begin(output_buffer) + output_end_ptr,
                       std::begin(io_pre.num) + (x << 2), 4),
                           output_end_ptr += 4;
            }
        }

        memcpy(std::begin(output_buffer) + output_end_ptr,
               std::begin(buf) + i + 4, TWELVE - i);
        output_end_ptr += TWELVE - i;
    }

    template <typename T_>
    IO &operator << (T_ &&x) {
        using T = typename std::remove_cv <
                  typename std::remove_reference<T_>::type >::type;
        static_assert(Internal::is_custom<T>::value or Internal::is_default<T>::value or
                      Internal::is_iterable<T>::value or Internal::is_applyable<T>::value);

        if constexpr(Internal::is_custom<T>::value) {
            write_int(x.get());
        } else if constexpr(Internal::is_default<T>::value) {
            if constexpr(Internal::is_bool<T>::value) {
                write_bool(x);
            } else if constexpr(Internal::is_string<T>::value) {
                write_string(x);
            } else if constexpr(Internal::is_char<T>::value) {
                write_char(x);
            } else if constexpr(Internal::is_int<T>::value) {
                write_int(x);
            }
        } else if constexpr(Internal::is_iterable<T>::value) {
            // strings are immune
            using E = decltype(*std::begin(x));
            constexpr char sep = needs_newline<E> ? '\n' : ' ';
            int i = 0;

            for (const auto &y : x) {
                if (i++)
                    write_char(sep);

                operator<<(y);
            }
        } else if constexpr(Internal::is_applyable<T>::value) {
            // strings are immune
            constexpr char sep =
                (any_needs_newline <
                 T, std::make_index_sequence<std::tuple_size_v<T> >>::value)
                ? '\n'
                : ' ';
            int i = 0;
            std::apply(
            [this, &sep, &i](auto const & ... y) {
                (((i++ ? write_char(sep) : void()), this->operator<<(y)),
                 ...);
            },
            x);
        }

        return *this;
    }
    IO &operator << (IO<SAFETY_CHECKS> &(*func)(IO<SAFETY_CHECKS> &)) {
        return func(*this);
    }
    IO *tie(std::nullptr_t) {
        return this;
    }
    inline void sync_with_stdio(bool) {}
};
IO<false> Io(stdin, stdout);

template <const bool SAFETY_CHECKS>
FastIO::IO<SAFETY_CHECKS> &endl(FastIO::IO<SAFETY_CHECKS> &os) {
    os.write_char('\n');
    os.flush();
    return os;
}

#define cin FastIO::Io
#define cout FastIO::Io

};
using FastIO::endl;
/*/-----------------------------Code begins----------------------------------/*/
// https://loj.ac/s/1481088
// template <typename _Tp, typename _Fp, typename _Compare = std::less<void>>
// bool chmax(_Tp &a, const _Fp &b, _Compare __comp = _Compare()) { return __comp(a, b) ? a = b, true : false; }
// template <typename _Tp, typename _Fp, typename _Compare = std::less<void>>
// bool chmin(_Tp &a, const _Fp &b, _Compare __comp = _Compare()) { return __comp(b, a) ? a = b, true : false; }
namespace OY {
template <typename _Tp>
struct HLPP {
    struct _RawEdge {
        uint32_t from, to;
        _Tp cap;
    };
    struct _Edge {
        uint32_t to, rev;
        _Tp cap;
        bool operator>(const _Edge &other) const {
            return cap > other.cap;
        }
    };
    std::vector<_RawEdge> m_rawEdges;
    std::vector<_Edge> m_edges;
    std::vector<uint32_t> m_starts;
    uint32_t m_vertexNum;
    HLPP(uint32_t __vertexNum, uint32_t __edgeNum) : m_starts(__vertexNum + 1, 0), m_vertexNum(__vertexNum) {
        m_rawEdges.reserve(__edgeNum);
    }
    void addEdge(uint32_t __a, uint32_t __b, _Tp __cap) {
        m_rawEdges.push_back({__a, __b, __cap});
    }
    void build() {
        for (auto &[from, to, cap] : m_rawEdges)
            if (from != to) {
                m_starts[from + 1]++;
                m_starts[to + 1]++;
            }

        std::partial_sum(m_starts.begin(), m_starts.end(), m_starts.begin());
        m_edges.resize(m_starts.back());
        uint32_t cursor[m_vertexNum];
        std::copy(m_starts.begin(), m_starts.begin() + m_vertexNum, cursor);

        for (auto &[from, to, cap] : m_rawEdges)
            if (from != to) {
                m_edges[cursor[from]] = {to, cursor[to], cap};
                m_edges[cursor[to]++] = {from, cursor[from]++, 0};
            }
    }
    template <typename _Compare = std::greater<_Edge>>
    void buildSorted(_Compare __comp = _Compare()) {
        build();

        for (uint32_t i = 0; i < m_vertexNum; i++) {
            uint32_t start = m_starts[i], end = m_starts[i + 1];
            std::sort(m_edges.begin() + start, m_edges.begin() + end, __comp);

            for (uint32_t j = start; j < end; j++)
                m_edges[m_edges[j].rev].rev = j;
        }
    }
    _Tp calc(uint32_t __source, uint32_t __target, _Tp __infiniteCap = std::numeric_limits<_Tp>::max() / 2) {
        uint32_t queue[m_vertexNum], height[m_vertexNum], ex_next[m_vertexNum * 2], gap_prev[m_vertexNum * 2],
                 gap_next[m_vertexNum * 2], ex_highest = 0, gap_highest = 0, discharge_count, it[m_vertexNum],
                                            end[m_vertexNum];
        _Tp ex[m_vertexNum];
        auto ex_insert = [&](uint32_t i, uint32_t h) {
            ex_next[i] = ex_next[m_vertexNum + h];
            ex_next[m_vertexNum + h] = i;
            ex_highest = max(ex_highest, h);
        };
        auto gap_insert = [&](uint32_t i, uint32_t h) {
            gap_prev[i] = m_vertexNum + h;
            gap_next[i] = gap_next[m_vertexNum + h];
            gap_prev[gap_next[i]] = gap_next[gap_prev[i]] = i;
            gap_highest = max(gap_highest, h);
        };
        auto gap_erase = [&](uint32_t i) {
            gap_next[gap_prev[i]] = gap_next[i];
            gap_prev[gap_next[i]] = gap_prev[i];
        };
        auto ex_add = [&](uint32_t i, _Tp f) {
            ex[i] += f;

            if (ex[i] == f)
                ex_insert(i, height[i]);
        };
        auto ex_remove = [&](uint32_t i, _Tp f) {
            ex[i] -= f;
        };
        auto update_height = [&](uint32_t i, uint32_t h) {
            if (~height[i])
                gap_erase(i);

            height[i] = h;

            if (~h) {
                gap_insert(i, h);

                if (ex[i] > 0)
                    ex_insert(i, h);
            }
        };
        auto global_relabel = [&] {
            discharge_count = 0;
            std::iota(ex_next + m_vertexNum, ex_next + m_vertexNum * 2, m_vertexNum);
            std::iota(gap_prev + m_vertexNum, gap_prev + m_vertexNum * 2, m_vertexNum);
            std::iota(gap_next + m_vertexNum, gap_next + m_vertexNum * 2, m_vertexNum);
            std::fill(height, height + m_vertexNum, -1);
            height[__target] = 0;
            uint32_t head = 0, tail = 0;
            queue[tail++] = __target;

            while (head < tail)
                for (uint32_t from = queue[head++], cur = m_starts[from], end = m_starts[from + 1]; cur < end; cur++)
                    if (auto &[to, rev, cap] = m_edges[cur]; m_edges[rev].cap && height[to] > height[from] + 1) {
                        update_height(to, height[from] + 1);
                        queue[tail++] = to;
                    }
        };
        auto push = [&](uint32_t from, uint32_t to, uint32_t rev, _Tp & cap, _Tp f) {
            ex_remove(from, f);
            ex_add(to, f);
            cap -= f;
            m_edges[rev].cap += f;
        };
        auto discharge = [&](uint32_t i) {
            uint32_t h = m_vertexNum;
            uint32_t pos = it[i];

            for (uint32_t &cur = it[i]; cur < end[i]; cur++)
                if (auto &[to, rev, cap] = m_edges[cur]; cap) {
                    if (height[i] == height[to] + 1) {
                        push(i, to, rev, cap, std::min(ex[i], cap));

                        if (!ex[i])
                            return;
                    } else
                        h = min(h, height[to]);
                }

            it[i] = m_starts[i];

            for (uint32_t &cur = it[i]; cur < pos; cur++)
                if (auto &[to, rev, cap] = m_edges[cur]; cap) {
                    if (height[i] == height[to] + 1) {
                        push(i, to, rev, cap, std::min(ex[i], cap));

                        if (!ex[i])
                            return;
                    } else
                        h = min(h, height[to]);
                }

            discharge_count++;

            if (gap_next[gap_next[m_vertexNum + height[i]]] < m_vertexNum)
                update_height(i, h == m_vertexNum ? -1 : h + 1);
            else {
                uint32_t oldh = height[i];

                for (h = oldh; h <= gap_highest; h++)
                    while (gap_next[m_vertexNum + h] < m_vertexNum) {
                        uint32_t j = gap_next[m_vertexNum + h];
                        height[j] = -1;
                        gap_erase(j);
                    }

                gap_highest = oldh - 1;
            }
        };

        for (uint32_t i = 0; i < m_vertexNum; i++)
            it[i] = m_starts[i];

        for (uint32_t i = 0; i < m_vertexNum; i++)
            end[i] = m_starts[i + 1];

        std::fill(ex, ex + m_vertexNum, 0);
        global_relabel();
        ex_add(__source, __infiniteCap);
        ex_remove(__target, __infiniteCap);

        while (~ex_highest) {
            while (true) {
                uint32_t i = ex_next[m_vertexNum + ex_highest];

                if (i >= m_vertexNum)
                    break;

                ex_next[m_vertexNum + ex_highest] = ex_next[i];

                if (height[i] != ex_highest)
                    continue;

                discharge(i);

                if (discharge_count >= 4 * m_vertexNum)
                    global_relabel();
            }

            ex_highest--;
        }

        return ex[__target] + __infiniteCap;
    }
};
}


template <typename Cap = int>
struct HLPP {
    struct Edge {
        int j, q;
        Cap x;
    };
    int N, K = 0;
    vector<vector<Edge>> G;
    HLPP(int n): N(n), G(N) { }
    void addEdge(int i, int j, Cap x, Cap y = 0) {
        int p = G[i].size(), q = G[j].size();
        G[i].push_back({j, q, x});
        G[j].push_back({i, p, y});
    }
    Cap calc(int src, int sink, Cap inf = numeric_limits<Cap>::max()) {
        vector<int> pos(N);
        vector<Cap> ex(N);
        int queue[N], height[N], ex_next[N * 2], gap_prev[N * 2], gap_next[N * 2];
        int ex_highest = 0, gap_highest = 0, discharge_count = 0;
        auto ex_insert = [&](int i, int h) {
            ex_next[i] = ex_next[N + h];
            ex_next[N + h] = i;
            ex_highest = max(ex_highest, h);
        };
        auto gap_insert = [&](int i, int h) {
            gap_prev[i] = N + h;
            gap_next[i] = gap_next[N + h];
            gap_prev[gap_next[i]] = gap_next[gap_prev[i]] = i;
            gap_highest = max(gap_highest, h);
        };
        auto gap_erase = [&](int i) {
            gap_next[gap_prev[i]] = gap_next[i];
            gap_prev[gap_next[i]] = gap_prev[i];
        };
        auto ex_add = [&](int i, Cap f) {
            ex[i] += f;

            if (ex[i] == f)
                ex_insert(i, height[i]);
        };
        auto update_height = [&](int i, int h) {
            if (height[i] != N + 1)
                gap_erase(i);

            height[i] = h;

            if (h == N + 1)
                return;

            gap_insert(i, h);

            if (ex[i] > 0)
                ex_insert(i, h);
        };
        auto global_relabel = [&] {
            discharge_count = 0;
            iota(ex_next + N, ex_next + N * 2, N);
            iota(gap_prev + N, gap_prev + N * 2, N);
            iota(gap_next + N, gap_next + N * 2, N);
            fill(height, height + N, N + 1);
            height[sink] = 0;
            int head = 0, tail = 0;
            queue[tail++] = sink;

            while (head < tail) {
                int i = queue[head++];

                for (auto& [j, q, x] : G[i]) {
                    if (!G[j][q].x || height[j] <= height[i] + 1)
                        continue;

                    update_height(j, height[i] + 1);
                    queue[tail++] = j;
                }
            }
        };
        auto discharge = [&](int i) {
            auto &v = ex[i];
            int h = height[i], nh = N;

            for (int &p = pos[i], n = G[i].size(); n--; p = (p ? : G[i].size()) - 1) {
                auto& [j, q, x] = G[i][p];

                if (!x)
                    continue;

                if (h != height[j] + 1) { // i == sink?
                    nh = min(nh, height[j]);
                    continue;
                }

                auto f = min(v, x);
                v -= f;
                ex_add(j, f);
                x -= f;
                G[j][q].x += f;

                if (!v)
                    return;
            }

            discharge_count++;

            if (gap_next[gap_next[N + h]] < N) {
                update_height(i, nh + 1);
                return;
            }

            for (int oldh = h; gap_highest >= oldh; gap_highest--)
                while (gap_next[N + gap_highest] < N) {
                    int j = gap_next[N + gap_highest];
                    height[j] = N + 1;
                    gap_erase(j);
                }
        };
        global_relabel();
        ex_add(src, inf);
        ex[sink] -= inf;

        while (~ex_highest) {
            int i = ex_next[N + ex_highest];

            if (i >= N) {
                ex_highest--;
                continue;
            }

            ex_next[N + ex_highest] = ex_next[i];

            if (height[i] != ex_highest)
                continue;

            discharge(i);

            if (discharge_count >= 4 * N)
                global_relabel();
        }

        return ex[sink] + inf;
    }
};
int main() {

    cin.tie(nullptr) -> sync_with_stdio(false);
    uint32_t n, m, s, t;
    cin >> n >> m >> s >> t;
    OY::HLPP<uint32_t> G(n, m);

    for (int i = 0; i < m; i++) {
        uint32_t a, b;
        uint32_t c;
        cin >> a >> b >> c;
        G.addEdge(a - 1, b - 1, c);
    }

    G.build();
    cout << G.calc(s - 1, t - 1);
}