Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

Vasya has recently got a job as a cashier at a local store. His day at work is L minutes…

  1. User

    Vasya has recently got a job as a cashier at a local store. His day at work is L minutes long. Vasya has already memorized n regular customers, the i-th of which comes after t_{i} minutes after the beginning of the day, and his service consumes l_{i} minutes. It is guaranteed that no customer will arrive while Vasya is servicing another customer.

    Vasya is a bit lazy, so he likes taking smoke breaks for a minutes each. Those breaks may go one after another, but Vasya must be present at work during all the time periods he must serve regular customers, otherwise one of them may alert his boss. What is the maximum number of breaks Vasya can take during the day? Input

    The first line contains three integers n, L and a (0 ≤ n ≤ 10^{5}, 1 ≤ L ≤ 10^{9}, 1 ≤ a ≤ L).

    The i-th of the next n lines contains two integers t_{i} and l_{i} (0 ≤ t_{i} ≤ L - 1, 1 ≤ l_{i} ≤ L). It is guaranteed that t_{i} + l_{i} ≤ t_{i + 1} and t_{n} + l_{n} ≤ L.

    Output

    Output one integer — the maximum number of breaks.

    Examples

    Input

    2 11 3 0 1 1 1

    Output

    3

    Input

    0 5 2

    Output

    2

    Input

    1 3 2 1 2

    Output

    0

    Note

    In the first sample Vasya can take 3 breaks starting after 2, 5 and 8 minutes after the beginning of the day.

    In the second sample Vasya can take 2 breaks starting after 0 and 2 minutes after the beginning of the day.

    In the third sample Vasya can't take any breaks.

  2. DeepSeek Assistant

    We need to solve: Vasya's work day is L minutes long. There are n customers, each arrives at time t_i and takes l_i minutes to serve. Guarantee that no overlap: t_i + l_i ≤ t_{i+1} (for i from 1 to n-1) and t_n + l_n ≤ L. So the service intervals are non-overlapping and within [0, L]. Vasya can take breaks of exactly a minutes each. Breaks can be back-to-back. He must be present during the service intervals. He can take breaks any time when not serving customers, including before the first customer, between customers, and after the last customer until L. Breaks must fit entirely into the free time intervals? The problem says: "What is the maximum number of breaks Vasya can take during the day?" He takes breaks of exactly a minutes each. He can take them at any times as long as they don't overlap with service intervals. Since breaks are exactly a minutes and can be consecutive, the maximum number is essentially the total free time divided by a, but careful: Breaks cannot be partial; they must be of exactly a minutes. So the maximum number is the floor of (total free time) / a. However, there might be constraints due to intervals: if free time is not contiguous, you can still take multiple breaks, but they must fit into the intervals. Since we can break them across intervals, the total number of breaks possible equals sum over free intervals of floor(length of interval / a). Because each break lasts exactly a and cannot span across intervals. So answer = sum_{i=0 to n} floor(gap_i / a), where gap_0 = t_1 - 0 (if n>0; if n=0, gap_0 = L), gap_i = t_{i+1} - (t_i + l_i) for i=1..n-1, gap_n = L - (t_n + l_n). This is straightforward.

    But caution: n can be 0, then answer = floor(L / a). Also t_i + l_i ≤ t_{i+1}, so gaps are non-negative.

    Edge cases: When n=0, input only has n, L, a. So we handle.

    Complexity: O(n). n up to 100k, so fine.

    Let's double-check examples:

    Example1: n=2, L=11, a=3. Customers: (0,1) and (1,1). But wait: t1=0, l1=1 => service ends at 1. t2=1, l2=1 => service ends at 2. Gap0 = t1 - 0 = 0. Gap1 = t2 - (t1+l1) = 1 - 1 = 0. Gap2 = L - (t2+l2) = 11 - 2 = 9. floor(9/3)=3. Output 3. matches.

    Example2: n=0, L=5, a=2 => floor(5/2)=2. Output 2. matches.

    Example3: n=1, L=3, a=2, customer (1,2). Service from 1 to 3 (since 1+2=3). Gap0 = t1 - 0 = 1. floor(1/2)=0. Gap1 = L - (t1+l1) = 3-3=0 => total 0. Output 0. matches.

    Thus solution is simple.

    Implementation: read n, L, a. Initialize prev_end = 0, ans = 0. For each customer: read t, l. gap = t - prev_end. ans += gap // a. Then set prev_end = t + l. After loop, gap = L - prev_end. ans += gap // a. Print ans.

    Be careful with integer division.

    We need to handle n=0: loop zero times, prev_end = 0, then gap = L - 0 = L, ans = L // a.

    That's all.

    Now produce final answer in Python.

    We need to write code with fast I/O? Not necessary but okay.

    Time complexity: O(n). Memory: O(1).

    We'll produce final solution.

    But as per instruction: we need to output code only? The user says: "Please solve the problem." They likely expect solution in code. We'll output Python code.

    We'll also include some explanation? The typical answer might be just code. But they asked "Please solve the problem." They probably want solution explanation and code. Since we are ChatGPT, we can output both? But the instruction says: "You are a competitive programming AI. Provide a solution in the requested language (usually C++ or Python)." Typically we output code block. I'll provide Python code with explanation.

    Thus final answer: python implementation.

    Potential pitfalls: Use integer division //.

    Will produce:

    def solve(): import sys data = sys.stdin.read().strip().split() if not data: return it = iter(data) n = int(next(it)) L = int(next(it)) a = int(next(it)) ans = 0 prev_end = 0 for _ in range(n): t = int(next(it)) l = int(next(it)) gap = t - prev_end ans += gap // a prev_end = t + l gap = L - prev_end ans += gap // a print(ans)

    if name == "main": solve()

    That's it. ```python

    import sys

    def solve() -> None: data = sys.stdin.read().strip().split() if not data: return it = iter(data) n = int(next(it)) L = int(next(it)) a = int(next(it))

    ans = 0
    prev_end = 0  # end time of the previous customer (or 0 initially)
    
    for _ in range(n):
        t = int(next(it))
        l = int(next(it))
        gap = t - prev_end
        ans += gap // a
        prev_end = t + l
    
    # remaining time after the last customer
    gap = L - prev_end
    ans += gap // a
    
    print(ans)
    

    if name == "main": solve()