{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eLabi-ribi\u003c/span\u003e 是一款新发布的STG游戏。众所周知,wor是一位\u003cspan class\u003d\"tex-font-style-it\"\u003e东方Project玩家\u003c/span\u003e。作为一位\u003cspan class\u003d\"tex-font-style-it\"\u003e东方Project玩家\u003c/span\u003e,他肯定想玩这样有趣的STG游戏。\u003c/p\u003e\n\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eLabi-ribi\u003c/span\u003e 有$$$n$$$个关卡。每个关卡的boss等级为$$$h_i$$$。只有当玩家的等级大于等于boss的等级时,玩家才能击败boss并通关这个关卡。在击败第$$$i$$$个boss后,剩余所有boss的等级将增加$$$a_i$$$点,玩家的等级将增加$$$b_i$$$点。\u003c/p\u003e\n\u003cp\u003ewor想挑战最难的关卡。因此,他想用最小的初始等级来通关所有关卡。你能告诉他需要的最小初始等级吗?\u003c/p\u003e\n\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eLabi-ribi\u003c/span\u003e 是一款很棒的游戏,所以每年都会有额外的DLC。现在已经有$$$q$$$个DLC了。对于每个DLC,wor都会耐心地玩一遍\u003cspan class\u003d\"tex-font-style-it\"\u003eLabi-ribi\u003c/span\u003e。同样,对于每个额外的DLC,wor想知道可以通关所有关卡所需的最小初始等级。你能帮他吗?\u003c/p\u003e\n"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数$$$n ~ (1 \\le n \\le 10^5)$$$,表示初始关卡的数量。\u003c/p\u003e\n\u003cp\u003e第二行包含$$$n$$$个整数$$$h_1, h_2, \\cdots, h_n ~ (-10^9 \\le h_i \\le 10^9)$$$,表示第$$$i$$$个boss的初始等级。\u003c/p\u003e\n\u003cp\u003e接下来的$$$n$$$行中,第$$$i$$$行包含两个整数$$$a_i, b_i ~ (-10^9 \\le a_i, b_i \\le 10^9)$$$。\u003c/p\u003e\n\u003cp\u003e第$$$n+3$$$行包含一个整数$$$q ~ (0 \\le q \\le 1000)$$$,表示额外的DLC数量。\u003c/p\u003e\n\u003cp\u003e接下来的$$$q$$$行中,第$$$i$$$行包含三个整数$$$h_i, a_i, b_i$$$,表示第$$$i$$$个DLC的参数。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e总共输出$$$q+1$$$行。\u003c/p\u003e\n\u003cp\u003e第一行包含一个整数,表示他需要通关所有关卡所需的最小初始等级。\u003c/p\u003e\n\u003cp\u003e接下来的$$$q$$$行中,第$$$i$$$行包含一个整数,表示在获得第$$$i$$$个额外的DLC后,他需要通关所有关卡所需的最小初始等级。\u003c/p\u003e"}},{"title":"样例 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003e输入\u003c/th\u003e\n \u003cth\u003e输出\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1 2 3\n1 2\n1 1\n1 0\n1\n4 1 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"样例 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003e输入\u003c/th\u003e\n \u003cth\u003e输出\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n100\n2 1\n2\n200 102 1\n1 1 100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e100\n201\n102\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}