All Tracks Algorithms Graphs Min-cut Problem

War in 1D Kingdom



A war has started in 1D Kingdom between Army and Rebels. Rebels have established bases at some places in 1D Kingdom. Location of all Army Soldiers, Rebels and Rebels' Bases are known. Rebels' Bases supplies weapons to Rebels who are within distance of $$d$$. Energy needed by a Soldier to kill a Rebel or to destroy a Rebels' Base is same as the distance between Soldier and Rebel (in case of killing Rebel) or distance between Soldier and Rebels' Base (in case of destroying Rebels' Base). Soldier returns to his initial position after killing Rebel or destroying Rebels' Base. A Rebel surrenders if there is no Rebels' Base to supply weapons to him within distance of $$d$$. Army wins when there is no Rebel who is alive and has not surrendered. You have to find the minimum energy required by Army to win the war. Energy spent by Army is sum of energy spent by Soldiers. Distance between point $$x$$ and point $$y$$ in 1D Kingdom is given by $$|x - y|$$. Also a Soldier can kill any number of Rebels or destroy any number of Rebels' Bases.

Input Format

First line contains four integers $$a$$, $$b$$, $$c$$ and $$d$$, where $$a$$ is number of Soldiers, $$b$$ is number of Rebels and $$c$$ is number of Rebels' Bases and $$d$$ is the distance parameter as mentioned above. Next line contains $$a$$ integers denoting the position of Soldiers in 1D Kingdom. Next line contains $$b$$ integers denoting the position of Rebels in 1D Kingdom. Next line contains $$c$$ integers denoting the position of Rebels' Bases in 1D Kingdom.

Output Format

Print single integer - minimum energy required by Army to win the war.

Input Constraints

  • $$1 <= a, b, c <= 200$$
  • $$1 <= d <= 10^9$$
  • $$1 <= $$position of Soldiers/Rebels/Rebels' Bases$$ <= 10^9$$

Note : There is no partial scoring in this problem.

Setter : Tanmay Patel

2 2 2 1
1 2
2 3
1 4

Soldier at position 1 will destroy Rebels' Base at position 1 with 0 energy spent and so Rebel at position 2 will surrender as he is within distance of 1. Soldier at position 2 will destroy Soldier at position 3 with 1 energy spent. Hence total energy spent = 1

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


View All Notifications