Woburn Challenge 2016-17 Round 2 - Senior Division

During its travels, the Starship Enterprise has come across a rather curious planet which appears to contain vast deposits of kironide, a rare and valuable mineral. Captain Kerk has ordered ~N~ ~(1 \le N \le 200\,000)~ of his crewmembers to go on an away mission to the planet's surface in order to confirm the sensors' readings. If all goes well, they'll be able to locate the kironide and collect some samples… before anything on the planet collects them as samples.

Each of the ~N~ crewmembers will need to be outfitted with a shirt, of course. It's standard Starfleet procedure for shirts to be manufactured on demand, with the use of a shirt replicator. The replicator is fed three Colour Component Chips (CCCs) - a red, green, and blue one - which determine the colour of the resulting shirt. Each CCC, in addition to corresponding to a particular colour component (either red, green, or blue), is encoded with an integral value between ~0~ and ~255~, inclusive. Kerk has ~N~ red CCCs with values ~R_{1 \dots N}~ at his disposal. He similarly has ~N~ green CCCs with values ~G_{1 \dots N}~, and ~N~ blue CCCs with values ~B_{1 \dots N}~.

Kerk may feed the CCCs into the shirt replicator in any combinations he'd like to in order to create ~N~ shirts, as long as the replicator is always given CCCs corresponding to all three different colour components at a time, and each of the ~3N~ CCCs is only used once.

A shirt is considered "red" if its red CCC's value is strictly larger than its other two CCCs' values. In other words, if a shirt was produced using red, green, and blue CCCs with values ~r~, ~g~, and ~b~, then it's red if both ~r > g~ and ~r > b~.

Unfortunate accidents have a way of happening to crewmembers wearing red shirts, so producing as few red shirts as possible would be beneficial. However, a strange anomaly has recently struck the Enterprise, which may be having unusual psychological effects on its crew, based on the value of ~Q~ ~(1 \le Q \le 2)~. If ~Q = 1~, then Kerk has remained resilient and is determined to arrange his CCCs such that as few as possible of the ~N~ shirts are red. Otherwise, if ~Q = 2~, then Kerk's psychological state has been compromised, and he'll instead maximize the number of red shirts produced!

In either case, please help estimate the number of "accidents" which might occur on the away mission by determining how many of the crewmembers will end up wearing red shirts.

In test cases worth ~4/20~ of the points, ~N \le 2000~ and ~B_i = 0~ for ~i = 1 \dots N~ (and in exactly ~50\%~ of these, ~Q = 1~).
In test cases worth another ~8/20~ of the points, ~N \le 2000~ (and in exactly ~50\%~ of these, ~Q = 1~).
In exactly ~50\%~ of the remaining test cases, ~Q = 1~.

Input Specification

The first line of input consists of two space-separated integers ~N~ and ~Q~.
The next line consists of ~N~ space-separated integers ~R_{1 \dots N}~.
The next line consists of ~N~ space-separated integers ~G_{1 \dots N}~.
The next line consists of ~N~ space-separated integers ~B_{1 \dots N}~.

Output Specification

Output a single integer - either the minimum possible number of red shirts that must be made if ~Q = 1~, or the maximum possible number that can be made if ~Q = 2~.

Sample Input 1

3 1
200 0 123
0 42 122
5 200 99

Sample Output 1

1

Sample Explanation 1

One optimal set of shirts is as follows (with each one notated as ~(r, g, b)~):

(200, 0, 200)
(0, 42, 99)
(123, 122, 5)

Of these, only the last one is red. Unfortunately, it's impossible for none of the shirts to be red.

Sample Input 2

3 2
200 0 123
0 42 122
5 200 99

Sample Output 2

2

Sample Explanation 2

One optimal set of shirts is as follows:

(200, 0, 99)
(0, 42, 200)
(123, 122, 5)