package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
	"strconv"
	"strings"
	"time"
)

// Item ...
type Item struct {
	time   time.Time
	depart int
}

// Schedule ...
type Schedule []Item

func (s Schedule) Len() int {
	return len(s)
}

func (s Schedule) Less(i, j int) bool {
	if s[j].time.Equal(s[i].time) { // Very important!
		return s[i].depart < s[j].depart
	}
	return s[j].time.After(s[i].time)
}

func (s Schedule) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

// Push ...
func (s *Schedule) Push(val interface{}) {
	*s = append(*s, val.(Item))
}

// Pop ...
func (s *Schedule) Pop() interface{} {
	n := s.Len()
	top := (*s)[n-1]
	*s = (*s)[:n-1]
	return top
}

func read2Time(s *bufio.Scanner) (time.Time, time.Time) {
	s.Scan()
	t := strings.Split(s.Text(), " ")
	t1, _ := time.Parse("15:04", t[0])
	t2, _ := time.Parse("15:04", t[1])
	return t1, t2
}

func readInt(s *bufio.Scanner) int {
	s.Scan()
	i, _ := strconv.ParseInt(s.Text(), 10, 32)
	return int(i)
}

func read2Int(s *bufio.Scanner) (int, int) {
	s.Scan()
	n := strings.Split(s.Text(), " ")
	n1, _ := strconv.ParseInt(n[0], 10, 32)
	n2, _ := strconv.ParseInt(n[1], 10, 32)
	return int(n1), int(n2)
}

func readInt64(s *bufio.Scanner) int64 {
	s.Scan()
	i, _ := strconv.ParseInt(s.Text(), 10, 32)
	return i
}

func readStr(s *bufio.Scanner) string {
	s.Scan()
	return s.Text()
}

func countTrains(scanner *bufio.Scanner) [][]int {
	caseCnt := readInt(scanner) // Read case count
	answer := make([][]int, caseCnt)
	for i := range answer {
		answer[i] = make([]int, 2)
	}
	for i := 0; i < caseCnt; i++ {
		var cd = time.Duration(readInt64(scanner)) * time.Minute
		cntAB, cntBA := read2Int(scanner)
		skdA, skdB := &Schedule{}, &Schedule{}
		for j := 0; j < cntAB; j++ {
			tOutA, tInB := read2Time(scanner)
			tInB = tInB.Add(cd)
			heap.Push(skdA, Item{tOutA, 1})
			heap.Push(skdB, Item{tInB, -1})
		}
		for j := 0; j < cntBA; j++ {
			tOutB, tInA := read2Time(scanner)
			tInA = tInA.Add(cd)
			heap.Push(skdA, Item{tInA, -1})
			heap.Push(skdB, Item{tOutB, 1})
		}
		currCntA, currCntB := 0, 0
		for skdA.Len() != 0 {
			top := heap.Pop(skdA)

			currCntA += top.(Item).depart
			if currCntA > answer[i][0] {
				answer[i][0] = currCntA
			}
		}
		for skdB.Len() != 0 {
			top := heap.Pop(skdB)
			currCntB += top.(Item).depart
			if currCntB > answer[i][1] {
				answer[i][1] = currCntB
			}
		}
	}
	return answer
}

func main() {
	inputFiles := []string{"B-small-practice.in", "B-large-practice.in", "test.in"}
	outputFiles := []string{"result-small.out", "result-large.out", "test.out"}
	const (
		small = iota
		large
		test
	)

	fileType := test

	fin, _ := os.Open(inputFiles[fileType])
	defer fin.Close()

	scanner := bufio.NewScanner(fin)
	answer := countTrains(scanner)

	fout, _ := os.Create(outputFiles[fileType])
	defer fout.Close()

	for i, v := range answer {
		s := fmt.Sprintf("Case #%d: %d %d\n", i+1, v[0], v[1])
		fout.WriteString(s)
	}
}