{"problem":{"name":"Bus Stops","description":{"content":"Takahashi is initially at his house and is about to visit Aoki's house. There are $N$ bus stops numbered $1$ to $N$ between the two houses, and Takahashi can move between them in the following ways: ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc319_e"},"statements":[{"statement_type":"Markdown","content":"Takahashi is initially at his house and is about to visit Aoki's house.\nThere are $N$ bus stops numbered $1$ to $N$ between the two houses, and Takahashi can move between them in the following ways:\n\n*   He can walk from his house to bus stop $1$ in $X$ units of time.\n*   For each $i = 1, 2, \\ldots, N-1$, a bus departs from bus stop $i$ at each time that is a multiple of $P_i$, and by taking this bus, he can get to bus stop $(i+1)$ in $T_i$ units of time. **Here, the constraints guarantee that $1 \\leq P_i \\leq 8$.**\n*   Takahashi can walk from bus stop $N$ to Aoki's house in $Y$ units of time.\n\nFor each $i = 1, 2, \\ldots, Q$, process the following query.\n\n> Find the earliest time that Takahashi can arrive at Aoki's house when he leaves his house at time $q_i$.\n\nNote that if he arrives at a bus stop exactly at the departure time of a bus, he can take that bus.\n\n## Constraints\n\n*   $2 \\leq N \\leq 10^5$\n*   $1 \\leq X, Y \\leq 10^9$\n*   $1 \\leq P_i \\leq 8$\n*   $1 \\leq T_i \\leq 10^9$\n*   $1 \\leq Q \\leq 2 \\times 10^5$\n*   $0 \\leq q_i \\leq 10^9$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $X$ $Y$\n$P_1$ $T_1$\n$P_2$ $T_2$\n$\\vdots$\n$P_{N-1}$ $T_{N-1}$\n$Q$\n$q_1$\n$q_2$\n$\\vdots$\n$q_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc319_e","tags":[],"sample_group":[["4 2 3\n5 4\n6 6\n3 1\n7\n13\n0\n710511029\n136397527\n763027379\n644706927\n447672230","34\n22\n710511052\n136397548\n763027402\n644706946\n447672250\n\nFor the first query, Takahashi can move as follows to arrive at Aoki's house at time $34$.\n\n*   Leave his house at time $13$.\n*   Walk from his house and arrive at bus stop $1$ at time $15$.\n*   Take the bus departing from bus stop $1$ at time $15$ and arrive at bus stop $2$ at time $19$.\n*   Take the bus departing from bus stop $2$ at time $24$ and arrive at bus stop $3$ at time $30$.\n*   Take the bus departing from bus stop $3$ at time $30$ and arrive at bus stop $4$ at time $31$.\n*   Walk from bus stop $4$ and arrive at Aoki's house at time $34$.\n\nFor the second query, Takahashi can move as follows and arrive at Aoki's house at time $22$.\n\n*   Leave his house at time $0$.\n*   Walk from his house and arrive at bus stop $1$ at time $2$.\n*   Take the bus departing from bus stop $1$ at time $5$ and arrive at bus stop $2$ at time $9$.\n*   Take the bus departing from bus stop $2$ at time $12$ and arrive at bus stop $3$ at time $18$.\n*   Take the bus departing from bus stop $3$ at time $18$ and arrive at bus stop $4$ at time $19$.\n*   Walk from bus stop $4$ and arrive at Aoki's house at time $22$."]],"created_at":"2026-03-03 11:01:14"}}