分数: 425 点
问题陈述
高桥将收到 N 呈现。
他有一个参数叫心情,是一个非负整数,每次收到礼物他的心情都会改变。 每个礼物都有三个参数:价值 P,情绪增加 A,情绪下降 B,他的情绪根据这些参数发生如下变化:
- 当该值 P 收到的礼物大于或等于他的心情,他对礼物很满意,他的心情增加 A.
- 当该值 P 收到的礼物低于他的心情,他对礼物感到失望,他的心情下降了 B。不过,如果他原本的心情不及 B,它变成 0.
的 i-th (1\le i\le N) 他收到的礼物很有价值 P _ i,情绪增加 A _ i,情绪下降 B _ i.
你被给予 Q 问题,所以请全部回答。 在 i-th (1\le i\le Q) 问题,给你一个非负整数 X _ i,所以回答以下问题:
找到高桥收到全部后的心情 N 当他的情绪最初出现时出现 X _ i.
约束
- 1\le N\le10000
- 1\le P _ i\le500\ (1\le i\le N)
- 1\le A _ i\le500\ (1\le i\le N)
- 1\le B _ i\le500\ (1\le i\le N)
- 1\le Q\le5\times10 ^ 5
- 0\le X _ i\le10 ^ 9\ (1\le i\le Q)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N P _ 1 A _ 1 B _ 1 P _ 2 A _ 2 B _ 2 \vdots P _ N A _ N B _ N Q X _ 1 X _ 2 \vdots X _ Q
输出
输出 Q 行。 的 i- 第行应包含以下问题的答案 i- 第一个问题。
示例输入 1
4 3 1 4 1 5 9 2 6 5 3 5 8 11 0 1 2 3 4 5 6 7 8 9 10
示例输出 1
6 0 0 0 5 6 0 0 0 0 0
当高桥最初的心情是 10,他的情绪变化如下:
- 值 3 第一份礼物不及他的心情 10,所以他的情绪随着情绪的降低而降低 4,他的心情变成 第二个礼物的 6.
- 值 1 低于他的心情 6,还有高桥的心情 6 小于心情下降 9,所以他的心情就变成了 0.
- 值 2 第三个礼物不亚于他的心情 0,所以他的情绪随着情绪的增加而增加 6,他的心情变成 第二个礼物的 6.
- 值 3 第四个礼物不及他的心情 6,还有高桥的心情 6 小于心情下降 8,所以他的心情就变成了 0.
所以,他最后的心情是 0.
示例输入 2
3 500 500 500 500 500 500 500 500 500 1 1000000000
示例输出 2
999998500
因为高桥的情绪太高,即使收到最好的礼物,他的情绪却不断下降。
示例输入 3
20 124 370 105 280 200 420 425 204 302 435 141 334 212 287 231 262 410 481 227 388 466 222 314 366 307 205 401 226 460 452 336 291 119 302 104 432 478 348 292 246 337 403 102 404 371 368 399 417 291 416 351 236 263 231 170 415 482 101 339 184 20 1162 1394 1695 2501 3008 3298 4053 4093 4330 5199 5302 5869 5875 6332 6567 7483 7562 7725 9723 9845
示例输出 3
339 339 339 339 339 339 339 339 339 339 339 339 339 389 339 643 722 885 2883 3005