The Handshake Problem

The Handshake Problem

Time limit: 1 s.
Memory limit: 256 MB

Muaath and Mousa live in Bishah, a city shaped like a number line that stretches forever in both directions — every integer is a valid position.

There are \(Q\) rounds that repeat in a cycle, over and over forever. In the \(i\)-th round, one person takes \(X_i\) steps:

  • If \(T_i = 1\), Muaath moves.
  • If \(T_i = 2\), Mousa moves.

If \(X_i\) is positive, he moves in the positive direction. If \(X_i\) is negative, they move in the negative direction. Either way, if a person is currently at position \(P\), they end up at position \(P + X_i\) after the round.

They don’t teleport — they walk one step per second, stopping at every position along the way. For example, if someone is at position \(3\) and moves \(+4\) steps, they visit positions \(4\), \(5\), \(6\), then land on \(7\), taking \(4\) seconds total.

Muaath starts at position \(A\) and Mousa starts at position \(B\). The \(Q\) rounds play out in order (round \(1\), round \(2\), …, round \(Q\)), and then immediately repeat from round \(1\) again, then round \(2\), and so on — forever.

Whenever they are at the same position at the same second, they shake hands. Find the first second on which they shake hands.

Input

The first line contains \(Q\), \(A\) and \(B\). \((-10^6 \le A, B \le 10^6), (1 \le Q \le 5 \cdot 10^5)\)

The next \(Q\) lines contain \(T_i\) and \(X_i\) each. \((T_i = 1 \text{ or } 2), (-10^6 \le X_i \le 10^6)\)

Output

Print a single integer, the second on which the first handshake will occur or print \(-1\) if that will never happen.

Scoring

Group Constraints Points
\(1\) if \(T_i = 1\) then \(X_i \le 0\) else \(X_i \ge 0\) \(9\)
\(2\) \((Q = 1), (-10^2 \le A, B, X_i \le 10^2)\) \(16\)
\(3\) \(\sum_{i:T_i=1} X_i = \sum_{i:T_i=2} X_i\) \(15\)
\(4\) \(Q = 1\) \(26\)
\(5\) if \(T_i = 1\) then \(X_i \le 0\) \(13\)
\(6\) — \(21\)

Subtask 1 means Muaath always moves in the non-positive direction, and Mousa always moves in the non-negative direction.

Subtask 3 means Muaath and Mousa move the same total distance over all Q rounds.

Examples

Input

2 -5 4
1 2
2 -2

Output

9

Input

3 0 10
2 -1
1 1
2 1

Output

26

Note

In the first sample testcase the following happens in each second:

Second Muaath Mousa
0 -5 4
1 -4 4
2 -3 4
3 -3 3
4 -3 2
5 -2 2
6 -1 2
7 -1 1
8 -1 0
9 0 0
Solution

Track the relative position

\[ D=\text{position of Muaath}-\text{position of Mousa}. \]

During a round, \(D\) moves by one in the same direction every second, so the values visited form an integer interval. After one complete cycle, \(D\) changes by a fixed value \(\Delta\), and the cycle takes a fixed number \(L\) of seconds.

For every round, let \([low,high]\) be its relative-position interval in the first cycle. In cycle \(c\), this becomes \([low+c\Delta,high+c\Delta]\). Using integer floor and ceiling division, find the smallest \(c\ge0\) for which this interval contains zero. This gives a handshake candidate for that round.

Check all rounds and take the earliest candidate. The complexity is \(O(Q)\) time and memory.

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

using int64 = long long;
using int128 = __int128_t;

struct Round {
    int64 change;
    int64 duration;
};

int64 floorDiv(int64 a, int64 b) {
    // b is positive.
    if (a >= 0) return a / b;
    return -((-a + b - 1) / b);
}

int64 ceilDiv(int64 a, int64 b) {
    return -floorDiv(-a, b);
}

void printInt128(int128 value) {
    if (value == 0) {
        cout << "0\n";
        return;
    }

    string digits;
    while (value > 0) {
        digits.push_back(char('0' + value % 10));
        value /= 10;
    }
    reverse(digits.begin(), digits.end());
    cout << digits << '\n';
}

int main() {
    int q;
    int64 a, b;
    cin >> q >> a >> b;

    vector<Round> rounds(q);
    int64 cycleChange = 0;
    int64 cycleLength = 0;

    for (Round& round : rounds) {
        int person;
        int64 x;
        cin >> person >> x;

        round.change = (person == 1 ? x : -x);
        round.duration = llabs(x);
        cycleChange += round.change;
        cycleLength += round.duration;
    }

    if (a == b) {
        cout << "0\n";
        return 0;
    }

    int64 relative = a - b;
    int64 timeInCycle = 0;
    const int128 INF = (int128(1) << 120);
    int128 answer = INF;

    for (const Round& round : rounds) {
        int64 start = relative;
        int64 finish = relative + round.change;
        int64 low = min(start, finish);
        int64 high = max(start, finish);

        bool possible = false;
        int64 cycle = 0;

        if (cycleChange == 0) {
            possible = (low <= 0 && 0 <= high);
        } else if (cycleChange > 0) {
            int64 first = max(0LL, ceilDiv(-high, cycleChange));
            int64 last = floorDiv(-low, cycleChange);
            if (first <= last) {
                possible = true;
                cycle = first;
            }
        } else {
            int64 step = -cycleChange;
            int64 first = max(0LL, ceilDiv(low, step));
            int64 last = floorDiv(high, step);
            if (first <= last) {
                possible = true;
                cycle = first;
            }
        }

        if (possible) {
            int64 shiftedStart = start + cycle * cycleChange;
            int64 secondsIntoRound = llabs(shiftedStart);
            int128 candidate = int128(cycle) * cycleLength
                            + timeInCycle + secondsIntoRound;
            answer = min(answer, candidate);
        }

        relative = finish;
        timeInCycle += round.duration;
    }

    if (answer == INF) {
        cout << -1 << '\n';
    } else {
        printInt128(answer);
    }
}