{"problem":{"name":"Flowers","description":{"content":"There are $N$ flowers arranged in a row. For each $i$ ($1 \\leq i \\leq N$), the height and the beauty of the $i$\\-th flower from the left is $h_i$ and $a_i$, respectively. Here, $h_1, h_2, \\ldots, h_N$","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"dp_q"},"statements":[{"statement_type":"Markdown","content":"There are $N$ flowers arranged in a row. For each $i$ ($1 \\leq i \\leq N$), the height and the beauty of the $i$\\-th flower from the left is $h_i$ and $a_i$, respectively. Here, $h_1, h_2, \\ldots, h_N$ are all distinct.\nTaro is pulling out some flowers so that the following condition is met:\n\n*   The heights of the remaining flowers are monotonically increasing from left to right.\n\nFind the maximum possible sum of the beauties of the remaining flowers.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N \\leq 2 × 10^5$\n*   $1 \\leq h_i \\leq N$\n*   $h_1, h_2, \\ldots, h_N$ are all distinct.\n*   $1 \\leq a_i \\leq 10^9$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$h_1$ $h_2$ $\\ldots$ $h_N$\n$a_1$ $a_2$ $\\ldots$ $a_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"dp_q","tags":[],"sample_group":[["4\n3 1 4 2\n10 20 30 40","60\n\nWe should keep the second and fourth flowers from the left. Then, the heights would be $1, 2$ from left to right, which is monotonically increasing, and the sum of the beauties would be $20 + 40 = 60$."],["1\n1\n10","10\n\nThe condition is met already at the beginning."],["5\n1 2 3 4 5\n1000000000 1000000000 1000000000 1000000000 1000000000","5000000000\n\nThe answer may not fit into a 32-bit integer type."],["9\n4 2 5 8 3 6 1 7 9\n6 8 8 4 6 3 5 7 5","31\n\nWe should keep the second, third, sixth, eighth and ninth flowers from the left."]],"created_at":"2026-03-03 11:01:14"}}