3579 - 公路 [CSP-J 2023]
题目描述
小苞准备开着车沿着公路自驾。
公路上一共有 n 个站点，编号为从 1 到 n。其中站点 i 与站点 i + 1 的距离为 v_i 公里。
公路上每个站点都可以加油，编号为 i 的站点一升油的价格为 a_i 元，且每个站点只出售整数升的油。
小苞想从站点 1 开车到站点 n，一开始小苞在站点 1 且车的油箱是空的。已知车的油箱足够大，可以装下任意多的油，且每升油可以让车前进 d 公里。问小苞从站点 1 开到站点 n，至少要花多少钱加油？
输入
输入的第一行包含两个正整数 n 和 d，分别表示公路上站点的数量和车每升油可以前进的距离。
输入的第二行包含 n - 1 个正整数 v_1, v_2\dots v_{n-1}，分别表示站点间的距离。
输入的第三行包含 n 个正整数 a_1, a_2 \dots a_n，分别表示在不同站点加油的价格。
输出
输出一行，仅包含一个正整数，表示从站点 1 开到站点 n，小苞至少要花多少钱加油。
样例
输入
5 4 10 10 10 10 9 8 9 6 5
输出
79
输入
617 7094 99439 91310 72032 86786 85010 91011 72699 53360 81355 91045 98213 83601 83094 52774 81687 81700 78267 98475 66321 86955 68179 81418 57336 97093 67445 88151 73807 89688 82937 75964 58094 88413 59170 79989 57365 61973 58706 95391 60519 52924 84406 68442 54090 67072 83159 88702 69347 74070 86117 75944 65038 53710 57041 82821 66684 97887 56929 56898 60092 67117 73892 90761 75919 87264 86582 77701 92875 84730 64984 93525 67798 87637 50125 55515 80991 52310 76120 85419 70210 69522 64773 66404 67092 87759 79980 67553 54982 50381 66920 53441 77793 82096 54261 70084 70443 66849 50218 90574 76656 60512 96721 93491 61516 91134 56377 87321 91483 92885 52001 66772 70181 79416 93264 66555 71733 74191 76051 96895 92045 95945 80648 94859 82475 79642 65700 55113 95319 52267 56193 57097 59232 85937 57269 83451 99584 50876 72636 98555 93870 52272 94450 86173 96077 60102 73408 84456 78855 76286 89227 75197 57156 67997 77458 80647 95102 55953 80711 81829 78399 53273 80838 61128 65134 85627 66860 79489 87993 59885 88293 55478 59460 90382 64099 94486 84543 73396 84248 77135 99714 86989 58146 71799 85608 70744 66059 94625 88576 78735 68951 80594 89039 61184 75154 79503 68904 52370 87539 87762 75083 66025 61647 66937 88693 63223 76336 77130 83977 54849 89012 54557 90688 51207 73496 82536 67827 56562 98237 64431 54357 81466 57606 71909 84189 82161 76547 52387 60602 86080 76391 89609 83727 89652 90869 90027 92220 52371 67294 64226 98463 67987 79096 96402 76281 68326 57657 93493 85527 50958 85304 72297 72629 85519 78819 77414 62111 60417 98445 87082 53911 74199 68719 71872 84037 97235 54462 84487 74331 87687 61850 58825 55652 61943 61785 75908 84633 70354 75899 57148 82750 51833 60734 91647 96709 67654 50178 78786 81916 61058 73906 75491 93152 74614 95866 52256 66863 88948 77532 52114 54625 53695 73272 67437 69294 85630 74289 82847 76044 67663 75425 94257 53137 53198 58606 75399 87781 94128 54243 87813 88068 87197 62531 92402 64714 86960 74003 52769 80014 82454 62036 51228 54179 90246 64329 88250 57700 75397 76558 81195 86939 85649 88053 71879 77591 51686 50136 99629 67246 50764 64444 61404 99490 60150 92271 84538 91937 95600 80677 98953 74166 74644 59696 97487 64352 88775 61878 79024 87480 82499 83914 67279 65114 92053 78851 82411 99298 92909 67647 85619 85461 50914 65304 76944 64352 52709 63760 93573 53960 50390 61068 97567 98044 82015 83554 90046 83609 69061 85176 71695 89654 89167 61827 50764 85086 76607 95998 85553 94742 57934 69592 79272 99237 50936 77974 93006 51893 66180 94594 96813 59654 89702 51594 71716 63578 71767 61714 68983 88213 80324 97975 81540 68446 55315 87269 87581 76341 86262 98402 61305 83168 97663 59453 72280 96857 85294 50827 55093 84685 63462 76626 82052 78035 50632 91998 82517 73594 66775 65568 72456 64716 59321 77944 99979 94905 75336 79960 50157 65139 50294 98810 78191 87558 59458 60024 53661 61048 52367 88716 97947 85345 70374 66841 80087 66610 52496 55394 91990 57267 64731 63788 72480 71365 83105 51334 66315 73781 90437 90065 54656 86290 89935 81965 82018 56229 93662 99695 81101 61083 79649 77899 88986 78026 96761 96349 85160 77207 88490 95095 97401 96489 88727 64250 96674 88868 96854 52163 88445 74765 87834 56218 99927 86601 74377 94169 57467 73174 54049 54307 77834 96891 70882 68689 86786 59447 71785 51159 61098 79171 88230 65235 72346 57068 60741 64975 75990 80022 64581 58938 65560 67097 50840 73720 76701 60547 54160 98270 83182 82826 68028 81894 72701 52909 76623 69035 92624 50948 86639 95955 93757 98038 70502 64707 91346 56565 94822 85221 55227 54300 60711 91611 80327 76571 51683 62373 63764 82249 56368 57950 80485 62635 58232 86069 74240 73033 85189 63515 97063 52305 62297 84501 52332 76872 93230 91310 50769 55364 65848 124 123 154 170 156 176 121 145 196 127 191 107 128 178 100 171 128 127 129 200 170 188 132 147 156 112 191 152 110 195 156 136 162 101 176 141 151 132 144 139 194 104 175 171 177 163 113 176 190 156 150 198 103 198 169 185 187 194 185 119 133 124 107 107 119 188 192 121 192 139 196 179 122 146 199 131 197 156 116 129 132 199 124 152 137 186 165 152 122 107 161 142 141 198 114 132 170 195 112 187 170 143 175 144 104 126 127 163 110 142 188 184 111 117 198 110 117 177 164 180 133 133 141 114 103 168 149 110 174 173 139 120 149 109 125 142 139 105 105 157 126 106 139 115 197 130 120 124 116 100 194 134 117 183 121 107 131 174 133 129 126 172 104 185 106 178 172 133 111 141 154 100 165 138 171 198 113 110 146 149 142 168 128 101 193 185 106 110 140 142 182 118 125 143 160 124 144 131 168 177 142 196 130 110 135 131 172 151 138 124 138 192 191 187 151 127 128 128 124 188 127 149 153 171 105 195 152 195 177 130 122 187 102 175 157 175 184 167 102 105 118 126 117 143 192 154 177 145 118 172 146 157 130 169 114 110 153 101 124 192 138 193 172 119 102 132 124 136 139 140 150 103 196 163 144 182 152 150 196 108 177 177 126 124 106 118 197 119 122 168 167 148 132 163 143 169 158 122 157 178 180 180 158 194 147 177 147 187 152 103 116 197 133 133 131 174 131 112 118 136 168 116 152 175 174 177 152 172 189 127 200 155 118 194 158 103 123 144 128 111 118 193 173 182 164 105 109 170 131 102 162 183 130 180 191 101 118 154 126 149 165 114 108 186 130 174 194 162 136 199 108 184 102 117 148 162 131 172 177 109 102 164 143 105 151 105 185 145 106 190 141 159 157 168 104 150 193 128 176 141 174 152 152 157 169 175 126 139 122 136 143 126 108 108 101 158 156 149 126 178 151 163 109 109 102 111 168 177 127 187 106 138 154 148 164 184 153 198 131 106 197 150 128 173 178 101 189 102 128 177 109 109 185 150 180 156 130 170 188 129 158 103 170 179 128 186 103 121 108 105 116 110 162 117 134 191 183 197 160 142 140 171 140 121 102 179 127 171 184 184 101 126 112 169 134 137 144 154 106 147 155 101 198 165 171 106 140 104 147 140 171 141 192 156 190 142 141 101 180 178 155 112 116 120 109 158 200 128 156 193 194 189 176 101 151 111 121 169 183 167 139 150 138 133 169 128 187 155 166 132 165 163 117 169 104 177 125 179 106 106 112 193 122 147 140 146 132 104 150 125 171 107 140 199 113 113 171 115 119 200 195 184 132 110 149 190 116 115 135 115 179 159 136 100 192 108 120 181 186 170 187 181 171 160 107 131 134 172 159 171 165 129 122 153 197 177 127
输出
653526
说明
【样例 1 解释】
最优方案下：小苞在站点 1 买了 3 升油，在站点 2 购买了 5 升油，在站点 4 购买了 2 升油。
【数据范围】
对于所有测试数据保证：1 \leq n \leq 10^5，1 \leq d \leq 10^5，1 \leq v_i \leq 10^5，1 \leq a_i \leq 10^5。
| 测试点 | n \leq | 特殊性质 |
|---|---|---|
| 1\sim 5 | 8 | 无 |
| 6\sim 10 | 10^3 | 无 |
| 11\sim 13 | 10^5 | A |
| 14\sim 16 | 10^5 | B |
| 17\sim 20 | 10^5 | 无 |
- 特殊性质 A：站点 1 的油价最低。
- 特殊性质 B：对于所有 1 \leq i < n，v_i 为 d 的倍数。
来源
CSP-J 2023 T2
标签
