[SDCPC 2023] Orders

Luogu

IDLGP9556

Time1000ms

Memory1024MB

DifficultyP2

2023山东O2优化省赛/邀请赛

A factory receives $n$ orders at the beginning of day $1$. The $i$-th order can be described as two integers $a_i$ and $b_i$, indicating that at the end of day $a_i$, the factory needs to deliver $b_i$ products to the customer. Given that the factory can produce $k$ products each day, and at the beginning of day $1$ the factory has no product in stock, can the factory complete all orders? ## Input There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 100$) indicating the number of test cases. For each test case: The first line contains two integers $n$ and $k$ ($1 \le n \le 100$, $1 \le k \le 10^9$) indicating the number of orders and the number of products the factory can produce each day. For the following $n$ lines, the $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^9$) indicating that the $i$-th order require the factory to deliver $b_i$ products at the end of day $a_i$. ## Output For each test case output one line. If the factory can complete all orders output $\texttt{Yes}$, otherwise output $\texttt{No}$. [samples] ## Note For the first sample test case, the factory can produce $5$ products each day. - At the end of day $1$, there are $5$ products in stock so the factory can complete the $2$-nd order. After delivery, there are $2$ products left in stock. - At the end of day $6$, the factory produces $25$ more products. There are $27$ products in stock so the factory can complete the $1$-st and the $3$-rd order. After delivery, there are $0$ products left in stock. - At the end of day $8$, the factory produces $10$ more products. There are $10$ products in stock so the factory can complete the $4$-th order. After delivery, there are $9$ products left in stock. For the second sample test case, the factory can produce $100$ products each day. - At the end of day $3$, there are $300$ products in stock and the factory can complete the $1$-st order. After delivery, there are $100$ products left in stock. - At the end of day $4$, the factory produces $100$ more products. There are only $200$ products in stock so the factory cannot complete the $2$-nd order.

Samples

Input #1

Output #1

Yes
No

API Response (JSON)

{
  "problem": {
    "name": "[SDCPC 2023] Orders",
    "description": {
      "content": "A factory receives $n$ orders at the beginning of day $1$. The $i$-th order can be described as two integers $a_i$ and $b_i$, indicating that at the end of day $a_i$, the factory needs to deliver $b_i",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9556"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A factory receives $n$ orders at the beginning of day $1$. The $i$-th order can be described as two integers $a_i$ and $b_i$, indicating that at the end of day $a_i$, the factory needs to deliver $b_i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments