TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Course  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3346
  • Problem
  • P3346劳动节搬砖
    Limits : Time Limit : 10000 MS   Memory Limit : 524288 KB
    Judgment Tips : 1s,512MB
    Description

    劳动节要参与劳动,nodgd正在建筑工地上劳动。

    仓库中有 \(A\) 种砖头和 \(B\) 种水泥。把砖头或者水泥从仓库搬运到工地,都会让身上变得很脏。搬运第 \(i(1\leq i\leq A)\) 种砖头会在衣服上积累 \(a_i\) 克的灰尘,搬运第 \(j(1\leq j\leq B)\) 种水泥会在衣服上积累 \(b_j\) 克的灰尘。

    另外,使用特定的打包方式将砖头和水泥一起搬运,衣服上沾染的灰尘会单独搬运的灰尘总量少一些。这样的打包方式有 \(M\) 种:如果打包搬运第 \(x_i\) 种砖头和第 \(y_i\) 种水泥,衣服上沾染的灰尘会比单独搬运时减少 \(c_i\) 克。但是,不能同时使用多种打包方式。

    nodgd的任务是将一种砖头和一种水泥从仓库搬运到工地,想知道最少沾染多少灰尘。

    Input Format

    第一行3个整数 \(A,B,M\)
    第二行 \(A\) 个整数 \(a_1,\dots,a_A\)
    第三行 \(B\) 个整数 \(b_1,\dots,b_B\)
    第四行起的接下来 \(M\) 行,每行三个整数 \(x_i,y_i,c_i\)

    Output Format

    输出一个整数答案。

    Hint

    样例数据

    输入输出样例1
    样例输入
    2 3 1
    3 3
    3 3 3
    1 2 1
    
    样例输出
    5
    

    打包搬运第 $1$ 种砖头和第 $2$ 种水泥,沾染灰尘 \(=3+3-1=5\) 克。

    输入输出样例2
    样例输入
    1 1 2
    10
    10
    1 1 5
    1 1 10
    
    样例输出
    10
    

    不能同时选择多种打包方式,所有沾染灰尘 \(=10+10-10=10\) 克。

    输入输出样例3
    样例输入
    2 2 1
    3 5
    3 5
    2 2 2
    
    样例输出
    6
    

    分别搬运第 $1$ 种砖头和第 $1$ 种水泥。

    数据规模与约定

    输入的所有数据都是整数
    $1\leq A,B,M, a_i,b_i,c_i\leq 10^5$
    $1\leq x_i\leq A$
    $1\leq y_i\leq B$
    \(c_i\leq a_{x_i}+b_{y_i}\)


    Source  Atcoder HPC2020 B