牛客多校第十场 D

#include <bits/stdc++.h>
#define ll __int128
using namespace std;
const int maxn = 1e5+7;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
int n;
ll top;
ll a[maxn],m[maxn];
inline ll read()
{
  ll x=0,f=1;
  char ch=getchar();
  while(ch<'0'||ch>'9')
  {
      if(ch=='-')
          f=-1;
      ch=getchar();
  }
  while(ch>='0'&&ch<='9')
  {
      x=x*10+ch-'0';
      ch=getchar();
  }
  return x*f;
}
inline void write(ll x)
{
  if(x<0)
  {
      putchar('-');
      x=-x;
  }
  if(x>9)
      write(x/10);
  putchar(x%10+'0');
}
ll gcd(ll a,ll b)
{
  return b==0?a:gcd(b,a%b);
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
  if(b==0)
  {
      x=1,y=0;
      return a;
  }
  ll d=exgcd(b,a%b,x,y);
  ll z=x;x=y;y=z-y*(a/b);
  return d;
}
ll exChina(int n,ll *A,ll *M)
{
  ll a, b, c, d, x, y, t;
  for(int i=1; i<n; i++)
  {
      a = M[i-1], b = M[i];
      c = A[i] - A[i-1];
      d = exgcd(a, b, x, y);
      if(c%d) return -1;
      t = b/d;
      x = (x*(c/d)%t+t)%t;
      A[i] = A[i-1] + M[i-1]*x;
      M[i] = M[i]/d*M[i-1];
  }
  return A[n-1];
}
int main()
{
  scanf("%d",&n);
  top=read();
  for(int i=0;i<n;i++)
  {
      m[i]=read();
      a[i]=read();
  }
  ll ans=exChina(n,a,m);
  if(ans==-1)
      printf("he was definitely lying\n");
  else if(ans>top)
      printf("he was probably lying\n");
  else
  {
      write(ans);
      printf("\n");
  }
  return 0;
}