A. Borya's Diagnosis

Codeforces

IDCF879A

Time2000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

It seems that Borya is seriously sick. He is going visit _n_ doctors to find out the exact diagnosis. Each of the doctors needs the information about all previous visits, so Borya has to visit them in the prescribed order (i.e. Borya should first visit doctor 1, then doctor 2, then doctor 3 and so on). Borya will get the information about his health from the last doctor. Doctors have a strange working schedule. The doctor _i_ goes to work on the _s__i_\-th day and works every _d__i_ day. So, he works on days _s__i_, _s__i_ + _d__i_, _s__i_ + 2_d__i_, .... The doctor's appointment takes quite a long time, so Borya can not see more than one doctor per day. What is the minimum time he needs to visit all doctors? ## Input First line contains an integer _n_ — number of doctors (1 ≤ _n_ ≤ 1000). Next _n_ lines contain two numbers _s__i_ and _d__i_ (1 ≤ _s__i_, _d__i_ ≤ 1000). ## Output Output a single integer — the minimum day at which Borya can visit the last doctor. [samples] ## Note In the first sample case, Borya can visit all doctors on days 2, 3 and 4. In the second sample case, Borya can visit all doctors on days 10 and 11.

似乎 Borya 生病了。他需要拜访 #cf_span[n] 位医生以确定确切的诊断。每位医生都需要了解他之前所有的就诊记录，因此 Borya 必须按照规定的顺序就诊（即 Borya 应首先就诊医生 #cf_span[1]，然后是医生 #cf_span[2]，接着是医生 #cf_span[3]，依此类推）。Borya 将从最后一位医生那里获得他的健康信息。医生们的工作时间表很奇怪。第 #cf_span[i] 位医生从第 #cf_span[si] 天开始上班，之后每隔 #cf_span[di] 天工作一次。因此，他在第 #cf_span[si, si + di, si + 2di, ...] 天工作。由于每次就诊耗时很长，Borya 每天最多只能就诊一位医生。问他最少需要多少天才能看完所有医生？第一行包含一个整数 #cf_span[n] —— 医生的数量（#cf_span[1 ≤ n ≤ 1000]）。接下来的 #cf_span[n] 行每行包含两个数 #cf_span[si] 和 #cf_span[di]（#cf_span[1 ≤ si, di ≤ 1000]）。请输出一个整数 —— Borya 可以就诊最后一位医生的最早天数。在第一个样例中，Borya 可以在第 #cf_span[2]、#cf_span[3] 和 #cf_span[4] 天就诊所有医生。在第二个样例中，Borya 可以在第 #cf_span[10] 和 #cf_span[11] 天就诊所有医生。 ## Input 第一行包含一个整数 #cf_span[n] —— 医生的数量（#cf_span[1 ≤ n ≤ 1000]）。接下来的 #cf_span[n] 行每行包含两个数 #cf_span[si] 和 #cf_span[di]（#cf_span[1 ≤ si, di ≤ 1000]）。 ## Output 请输出一个整数 —— Borya 可以就诊最后一位医生的最早天数。 [samples] ## Note 在第一个样例中，Borya 可以在第 #cf_span[2]、#cf_span[3] 和 #cf_span[4] 天就诊所有医生。在第二个样例中，Borya 可以在第 #cf_span[10] 和 #cf_span[11] 天就诊所有医生。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of doctors. For each doctor $ i \in \{1, 2, \dots, n\} $, let $ s_i \in \mathbb{Z}^+ $ be the first working day and $ d_i \in \mathbb{Z}^+ $ be the periodic interval, so the doctor works on days $ \{ s_i + k \cdot d_i \mid k \in \mathbb{N}_0 \} $. **Constraints** 1. $ 1 \leq n \leq 1000 $ 2. $ 1 \leq s_i, d_i \leq 1000 $ for all $ i \in \{1, \dots, n\} $ **Objective** Find the minimum day $ D_n $ such that there exists a strictly increasing sequence of days $ D_1 < D_2 < \dots < D_n $, where for each $ i \in \{1, \dots, n\} $: - $ D_i \geq s_i $, - $ D_i \equiv s_i \pmod{d_i} $, - $ D_i \geq D_{i-1} + 1 $ (with $ D_0 = 0 $), and $ D_n $ is minimized.

Samples

Input #1

Output #1

Input #2

2
10 1
6 5

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Borya's Diagnosis",
    "description": {
      "content": "It seems that Borya is seriously sick. He is going visit _n_ doctors to find out the exact diagnosis. Each of the doctors needs the information about all previous visits, so Borya has to visit them in",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF879A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "It seems that Borya is seriously sick. He is going visit _n_ doctors to find out the exact diagnosis. Each of the doctors needs the information about all previous visits, so Borya has to visit them in...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "似乎 Borya 生病了。他需要拜访 #cf_span[n] 位医生以确定确切的诊断。每位医生都需要了解他之前所有的就诊记录，因此 Borya 必须按照规定的顺序就诊（即 Borya 应首先就诊医生 #cf_span[1]，然后是医生 #cf_span[2]，接着是医生 #cf_span[3]，依此类推）。Borya 将从最后一位医生那里获得他的健康信息。\n\n医生们的工作时间表很奇怪。第 #cf_...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of doctors.  \nFor each doctor $ i \\in \\{1, 2, \\dots, n\\} $, let $ s_i \\in \\mathbb{Z}^+ $ be the first working day and $ d_i \\in \\mathbb{Z}^+ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments