#2289. [GESP202409 五级] 小杨的武器

[GESP202409 五级] 小杨的武器

Description

⼩杨有 nn 种不同的武器,他对第 ii 种武器的初始熟练度为 cic_i

⼩杨会依次参加 mm 场战⽃,每场战⽃⼩杨只能且必须选择⼀种武器使⽤,假设⼩杨使⽤了第 ii 种武器参加了第 jj 场战⽃,战⽃前该武器的熟练度为 cic_i',则战⽃后⼩杨对该武器的熟练度会变为 ci+ajc_i'+a_j。需要注意的是,aja_j 可能是正数,00 或负数,这意味着⼩杨参加战⽃后对武器的熟练度可能会提⾼,也可能会不变,还有可能降低。

⼩杨想请你编写程序帮他计算出如何选择武器才能使得 mm 场战⽃后,⾃⼰对 nn 种武器的熟练度的最⼤值尽可能⼤

Input Format

第⼀⾏包含两个正整数 n,mn,m,含义如题⾯所⽰。

第⼆⾏包含 nn 个正整数 c1,c2,...,cnc_1,c_2,...,c_n,代表⼩杨对武器的初始熟练度。

第三⾏包含 mm 个正整数 a1,a2,...,ama_1,a_2,...,a_m,代表每场战⽃后武器熟练度的变化值。

Output Format

输出⼀个整数,代表 mm 场战⽃后⼩杨对 nn 种武器的熟练度的最⼤值最⼤是多少。

2 2
9 9
1 -1

10

Hint

样例解释

⼀种最优的选择⽅案为,第⼀场战⽃⼩杨选择第⼀种武器,第⼆场战⽃⼩杨选择第⼆种武器。

数据范围

子任务编号 数据点占比 nn mm
1 20%20 \% =1=1 105\leq 10^5
2 20%20\% 105\leq 10^5 =2=2
3 60%60\% 105\leq 10^5 105\leq 10^5

对于全部数据,保证有 1n,m1051 \leq n,m \leq 10^5104ci,ai104-10^4 \leq c_i,a_i \leq 10^4

Source

GESP五级202409