{"problem":{"name":"AtArcher","description":{"content":"Ringo is participating in an archery contest AtArcher. In AtArcher, a participant shoots $N$ arrows at a target on a number line to compete for the total score. The center of the target is at coordina","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc131_d"},"statements":[{"statement_type":"Markdown","content":"Ringo is participating in an archery contest AtArcher.\nIn AtArcher, a participant shoots $N$ arrows at a target on a number line to compete for the total score. The center of the target is at coordinate $0$. Based on where the arrow hits, the score of the shot is defined as follows.\n\n*   For $i = 0, 1, \\dots, M-1$, if the arrow hits a point whose distance from the center of the target is between $r_i$ and $r_{i+1}$, the score is $s_i$. If the distance is greater than $r_M$, the score is $0$. **If the arrow hits the boundary, the higher score is applied.**\n*   The closer to the center, the higher the score is. In other words, the following is satisfied.\n    *   $0 = r_0 \\lt r_1 \\lt \\cdots \\lt r_{M-1} \\lt r_M$\n    *   $s_0 \\gt s_1 \\gt \\cdots \\gt s_{M-1} \\gt 0$\n\nFor example, the figure below shows the score for a shot when $r = (0, 2, 7, 9), s = (100, 70, 30)$.\n\n![image](https://img.atcoder.jp/arc131/9c119e12092c684d21feea8d7c1f0f76.png)\n\nAdditionally, AtArcher has one special rule: the distance between any two arrows must always be at least $D$. Violating this rule disqualifies the participant, making the total score $0$.\nWhat is the maximum total score that Ringo can get from all the shots?\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^5$\n*   $1 \\leq M \\leq 10^5$\n*   $1 \\leq D \\leq 10^6$\n*   $0 = r_0 \\lt r_1 \\lt \\cdots \\lt r_{M-1} \\lt r_M \\leq 10^{11}$\n*   $10^{11} \\geq s_0 \\gt s_1 \\gt \\cdots \\gt s_{M-1} \\gt 0$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $D$\n$r_0$ $r_1$ $\\cdots$ $r_{M-1}$ $r_M$\n$s_0$ $s_1$ $\\cdots$ $s_{M-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc131_d","tags":[],"sample_group":[["3 3 3\n0 2 7 9\n100 70 30","270\n\nThis sample input corresponds to the case in the Problem Statement, with $D = 3$.\nFor example, if the $N = 3$ arrows hit the coordinates $-6, -2, 1$, they score $70, 100, 100$, respectively, for a total score of $270$, which is the maximum achievable.\n\n![image](https://img.atcoder.jp/arc131/3b9fbfbeaf90d953098e650d7b070e0d.png)\n\nNote that you cannot hit the $100$\\-point area with all the arrows to score $300$, because the distance between any two arrows must be at least $D = 3$, or you will be disqualified and score $0$."],["3 3 8\n0 2 7 9\n100 70 30","200\n\nThis sample input corresponds to the case in the Problem Statement, with $D = 8$.\nFor example, if the $N = 3$ arrows hit the coordinates $-7, 1, 9$, they score $70, 100, 30$, respectively, for a total score of $200$, which is the maximum achievable.\n\n![image](https://img.atcoder.jp/arc131/aefdd113cd212d29142783d0ffb1ea1e.png)"],["7 5 47\n0 10 40 100 160 220\n50 25 9 6 3","111\n\nFor example, if you shoot the arrows as shown in the following figure, you will score $111$ in total, which is the maximum.\n\n![image](https://img.atcoder.jp/arc131/2058c9b1e1deeea3bc6bae11da70b210.png)"],["100 1 5\n0 7\n100000000000","300000000000\n\nYou can shoot $N = 100$ arrows, but in order to avoid disqualification, at most $3$ arrows can hit the area with a positive score."],["15 10 85\n0 122 244 366 488 610 732 854 976 1098 1220\n10 9 8 7 6 5 4 3 2 1","119"]],"created_at":"2026-03-03 11:01:13"}}