{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"### Read problems statements in [Mandarin Chinese](https://www.codechef.com/download/translated/COOK128/mandarin/VALET.pdf), [Russian](https://www.codechef.com/download/translated/COOK128/russian/VALET.pdf), and [Bengali](https://www.codechef.com/download/translated/COOK128/bengali/VALET.pdf) as well.\r\n\r\nYour friend works as a valet where $N$ cars show up in a shift. The $i$-th car will arrive $T_i$ seconds after the current moment, and the car can wait for at most $Y_i$ seconds. That is, your friend can only start parking the car from time $T_i$ to $T_i+Y_i$ (inclusive).\r\n\r\nAdditionally, it takes $X_i$ time to park the $i$-th car, which means he cannot park any other cars for $X_i$ seconds starting from the time he starts parking the $i$-th car. It is known that no driver would like to wait for more time than it takes to park his car, so that $Y_i \u003c X_i$ for all $i$. The driver of the $i$-th car will pay $A_i$ coins as a tip to your friend if his car is parked. Note that he can start parking the next car immediately after he finishes parking the previous car.\r\n\r\nYour friend has asked you what will be the maximize possible earnings if he optimally chooses which cars to park and at what times.\r\n\r\n### Input:\r\n\r\n- The first line contains one single integer $N$ $(1 \\le N \\le 3 \\cdot 10^5)$ $-$ the number of cars.\r\n\r\n- The second line contains $N$ integers $T_1, T_2, \\ldots, T_n$ $-$ the time (in seconds) at which $i$-th car arrives.\r\n\r\n- The third line contains $N$ integers $X_1, X_2, \\ldots, X_n$ $-$ the time (in seconds) required to park the $i$-th car.\r\n\r\n- The fourth line contains $N$ integers $Y_1, Y_2, \\ldots, Y_n$ $-$ the maximum time (in seconds) for which the $i$-th car can wait.\r\n\r\n- The fifth line contains $N$ integers $A_1, A_2, \\ldots, A_n$ $-$ the tip which the $i$-th car driver gives after the car is parked.\r\n\r\n\r\n\r\n### Output:\r\nPrint a single integer $-$ the answer to the problem.\r\n\r\n### Constraints \r\n- $1\\le N\\le 3\\cdot 10^5$\r\n\r\n- $1\\le T_i\\le 4\\cdot 10^3$\r\n\r\n- $0\\le Y_i \u003c X_i\\le 4\\cdot 10^3$\r\n\r\n- $1\\le A_i\\le 10^9$"}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n5 8 11\r\n3 10 4\r\n1 0 1\r\n11 13 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e24\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\nIt is optimal to start parking the first car at $5$ seconds. We finish parking at $8$ seconds, and immediately start parking the second car."}}]}