```go
package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
	"sort"
)

type Improvement struct {
	id    int
	typ   int
	skill int
	val   int64
}

type Fraction struct {
	num   uint64
	den   uint64
	id    int
	typ   int
	skill int
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	buf := make([]byte, 1024*1024)
	scanner.Buffer(buf, 10*1024*1024)

	scanInt := func() int {
		scanner.Scan()
		res := 0
		for _, b := range scanner.Bytes() {
			res = res*10 + int(b-'0')
		}
		return res
	}

	scanInt64 := func() int64 {
		scanner.Scan()
		res := int64(0)
		for _, b := range scanner.Bytes() {
			res = res*10 + int64(b-'0')
		}
		return res
	}

	if !scanner.Scan() {
		return
	}
	resK := 0
	for _, b := range scanner.Bytes() {
		resK = resK*10 + int(b-'0')
	}
	k := resK

	n := scanInt()
	m := scanInt()

	a := make([]int64, k+1)
	for i := 1; i <= k; i++ {
		a[i] = scanInt64()
	}

	bestType1 := make([]Improvement, k+1)
	type2 := make([][]Improvement, k+1)
	var type3 []Improvement

	for j := 1; j <= n; j++ {
		typ := scanInt()
		skill := scanInt()
		b := scanInt64()
		imp := Improvement{id: j, typ: typ, skill: skill, val: b}
		if typ == 1 {
			if bestType1[skill].val < b {
				bestType1[skill] = imp
			}
		} else if typ == 2 {
			type2[skill] = append(type2[skill], imp)
		} else if typ == 3 {
			type3 = append(type3, imp)
		}
	}

	var fractions []Fraction

	for i := 1; i <= k; i++ {
		var adds []Improvement
		adds = append(adds, type2[i]...)
		if bestType1[i].val > a[i] {
			pseudo := bestType1[i]
			pseudo.val = pseudo.val - a[i]
			adds = append(adds, pseudo)
		}

		sort.Slice(adds, func(x, y int) bool {
			return adds[x].val > adds[y].val
		})

		curr := uint64(a[i])
		for _, add := range adds {
			num := curr + uint64(add.val)
			den := curr
			fractions = append(fractions, Fraction{
				num:   num,
				den:   den,
				id:    add.id,
				typ:   add.typ,
				skill: add.skill,
			})
			curr = num
		}
	}

	for _, mul := range type3 {
		fractions = append(fractions, Fraction{
			num:   uint64(mul.val),
			den:   1,
			id:    mul.id,
			typ:   mul.typ,
			skill: mul.skill,
		})
	}

	sort.Slice(fractions, func(i, j int) bool {
		f1 := fractions[i]
		f2 := fractions[j]
		hi1, lo1 := bits.Mul64(f1.num, f2.den)
		hi2, lo2 := bits.Mul64(f2.num, f1.den)
		if hi1 != hi2 {
			return hi1 > hi2
		}
		return lo1 > lo2
	})

	take := m
	if len(fractions) < m {
		take = len(fractions)
	}

	var selected1 []int
	var selected2 []int
	var selected3 []int

	for i := 0; i < take; i++ {
		f := fractions[i]
		if f.typ == 1 {
			selected1 = append(selected1, f.id)
		} else if f.typ == 2 {
			selected2 = append(selected2, f.id)
		} else if f.typ == 3 {
			selected3 = append(selected3, f.id)
		}
	}

	outw := bufio.NewWriter(os.Stdout)
	defer outw.Flush()

	fmt.Fprintln(outw, len(selected1)+len(selected2)+len(selected3))
	var out []int
	out = append(out, selected1...)
	out = append(out, selected2...)
	out = append(out, selected3...)

	if len(out) > 0 {
		for i, v := range out {
			if i > 0 {
				fmt.Fprint(outw, " ")
			}
			fmt.Fprint(outw, v)
		}
		fmt.Fprintln(outw)
	}
}
```