SOLVE

LATER

War in 1D Kingdom

Problem

Editorial

Analytics

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.

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.

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

**$$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

Explanation

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...

{"a4a09ee": "/pagelets/recommended-problems/algorithm/h-2/", "a4a097e": "/pagelets/show-submission/algorithm/h-2/", "a4a09d5": "/pagelets/problems-hint/algorithm/h-2/", "a4a09bb": "/pagelets/problem-author-tester/algorithm/h-2/", "a4a09a0": "/pagelets/suggested-problems/algorithm/h-2/"}

{}

realtime.hackerearth.com

80

7bdd026218f6f486890f51e5b1c8a095b81d5103

58a29e5cae2309f04b28

/realtime/pusher/auth/