using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

class Program
{
    public void Proc()
    {
        Reader.IsDebug = false;

        int[] inpt = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();

        long[,] Map = new long[inpt[0]+1, inpt[1]+1];

        this.FriendsList = new Friends[inpt[2]];

        int japariman = inpt[3];

        for (int i = 0; i < this.FriendsList.Length; i++)
        {
            this.FriendsList[i] = new Friends(i, Reader.ReadLine());
        }
        if (!this.FriendsList.Any(a => a.X == 0 && a.Y == 0))
        {
            Map[0, 0] = 1;
        }
        for (int i = 1; i <= inpt[0]; i++)
        {
            if(!FriendsList.Any(a=>a.X == i && a.Y == 0)) {
                Map[i, 0] = Map[i - 1, 0];
            }
        }
        for (int i = 1; i <= inpt[1]; i++)
        {
            if(!FriendsList.Any(a=>a.X == 0 && a.Y == i)) {
                Map[0, i] = Map[0, i - 1];
            }
        }
        for(int i=1; i<=inpt[0]; i++) {
            for(int j=1; j<=inpt[1]; j++) {
                if(!FriendsList.Any(a=>a.X == i && a.Y == j)) {
                    Map[i, j] = Map[i-1, j] + Map[i,j-1];
                }
            }
        }
        Ans ans = GetAns(Map, 0, japariman);
        Console.WriteLine(ans.WayCount);
        for (int i = 0; i < FriendsList.Length; i++)
        {
            int key = 1 << i;
            if ((ans.Flag & key) != 0)
            {
                Console.WriteLine(FriendsList[i].Name);
            }
        }
    }

    private Ans GetAns(long[,] map, int flag, int remain)
    {
        if (remain <= 0)
        {
            return new Ans(map[map.GetLength(0)-1, map.GetLength(1)-1], flag);
        }

        int w = map.GetLength(0);
        int h = map.GetLength(1);

        List<Friends> target = new List<Friends>();
        if (map[0, 0] == 0)
        {
            target.Add(FriendsList.Where(a => a.X == 0 && a.Y == 0).First());
        }
        else
        {
            long max = FriendsList.Where(a => map[a.X, a.Y] == 0).Select(a =>a.GetKaitu(map)).Max();
            target = FriendsList.Where(a => a.GetKaitu(map) == max).ToList();
        }

        Ans ans = new Ans(0, 0);

        foreach (Friends f in target)
        {
            long[,] subMap = GetMap(map, f.X, f.Y, f.GetKaitu(map));
            Ans ret = this.GetAns(subMap, flag + (1 << f.ID), remain - 1);
            if (ret.WayCount > ans.WayCount)
            {
                ans = ret;
            }
        }
        return ans;

    }

    private long[,] GetMap(long[,] basMap, int x, int y, long val)
    {
        int w = basMap.GetLength(0);
        int h = basMap.GetLength(1);
        long[,] newMap = new long[w, h];
        for(int i=0; i<w; i++) {
            for(int j=0; j<h; j++) {
                newMap[i,j] = basMap[i,j];
            }
        }
        if (x == 0 && y == 0)
        {
            for (int i = 0; i < w; i++)
            {
                newMap[i, 0] = val;
            }
            return GetMap(newMap, 0, 1, val);
        }
        else if (x == 0)
        {
            for (int i = y; i < h; i++)
            {
                newMap[0, i] = val;
            }
            return GetMap(newMap, 1, y, newMap[0, y] + newMap[1, y - 1]);
        }
        else if (y == 0)
        {
            for (int i = x; i < w; i++)
            {
                newMap[i, 0] = val;
            }
            return GetMap(newMap, x, 1, newMap[x - 1, 1] + newMap[x, 0]);
        }
        else
        {
            for (int i = x; i < w; i++)
            {
                for (int j = y; j < h; j++)
                {
                    newMap[i, j] = newMap[i - 1, j] + newMap[i, j - 1];
                }
            }
            return newMap;
        }
    }

    private struct Ans
    {
        public long WayCount;
        public int Flag;

        public Ans(long w, int f) {
            this.WayCount = w;
            this.Flag = f;
        }

    }

    private Friends[] FriendsList;

    private struct Friends
    {
        public int X;
        public int Y;
        public string Name;
        public int ID;

        public long GetKaitu(long[,] mp)
        {
            if (this.X == 0 && this.Y == 0)
            {
                return 1;
            }
            else if (this.X == 0)
            {
                return mp[0, this.Y - 1];
            }
            else if (this.Y == 0)
            {
                return mp[this.X - 1, 0];
            }
            return mp[this.X - 1, this.Y - 1];
        }

        public Friends(int id, string init)
        {
            this.ID = id;
            string[] tmp = init.Split(' ');
            this.X = int.Parse(tmp[0]);
            this.Y = int.Parse(tmp[1]);
            this.Name = tmp[2];
        }
    }




    public class Reader
    {
        public static bool IsDebug = true;
        private static String PlainInput = @"


1 2 1 1
0 1 serval


";
        private static System.IO.StringReader Sr = null;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (Sr == null)
                {
                    Sr = new System.IO.StringReader(PlainInput.Trim());
                }
                return Sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
    }
    static void Main()
    {
        Program prg = new Program();
        prg.Proc();
    }
}