DMOPC '18 Contest 6 P4 - Tank

View as PDF

Submit solution

Points: 10
Time limit: 2.5s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Kiran is playing a tactical RPG! His signature move is to field a tanky unit, end the turn, and watch all the enemies fail to kill it. He wants to figure out which of his N units is the best tank. Each unit has two corresponding defensive traits: defense and resistance. Defense, represented as u_i, mitigates physical attacks. Resistance, represented as v_i, mitigates magical attacks. More precisely, the amount of damage a unit takes from a physical attack is \max(\text{Att} - \text{Def}, 0) and the amount of damage a unit takes from a magical attack is \max(\text{Att} - \text{Res}, 0).

In the next battle, Kiran will need his tank to survive against P physical attacks and M magical attacks. The i^{\text{th}} physical attack will have attack stat a_i and the j^{\text{th}} magical attack will have attack stat b_j. Help Kiran determine which of his units will take the least total amount of damage.


1 \le u_i, v_i, a_i, b_i \le 1\,000\,000
1 \le N, P, M \le 200\,000

Input Specification

The first line will contain three space-separated integers, N, P, M.
The next N lines will each contain two space-separated integers, u_i and v_i, representing the defense stat and resistance stat of the i^{\text{th}} unit.
The following line will contain P space-separated integers, a_1, a_2, \dots, a_P, representing the physical attacks.
The final line will contain M space-separated integers, b_1, b_2, \dots, b_M, representing the magical attacks.

Output Specification

Output the index of the best tank for the next battle. If there are ties, output the smallest index.

Sample Input 1

3 4 2
40 32
37 29
33 41
33 42 36 39
48 45

Sample Output 1


Explanation for Sample 1

Kiran's first unit will take 0 + 2 + 0 + 0 = 2 damage from the physical attacks and 16 + 13 = 29 damage from the magical attacks, resulting in 31 total damage. Kiran's second unit will take 0 + 5 + 0 + 2 = 7 damage from the physical attacks and 19 + 16 = 35 damage from the magical attacks, resulting in 42 total damage. Kiran's third unit will take 0 + 9 + 3 + 6 = 18 damage from the physical attacks and 7 + 4 = 11 damage from the magical attacks, resulting in 29 damage. So Kiran should use his third unit.

Sample Input 2

4 3 3
37 26
37 19
40 24
38 26
51 47 50
62 43 46

Sample Output 2


Explanation for Sample 2

The total damage to each unit is 110, 131, 107, and 107 respectively. There is a tie between the third and fourth unit, so the smaller index, 3 is the answer.


There are no comments at the moment.