U483209 陶陶摘苹果

陶陶家的院子里有一棵苹果树，每到秋天树上就会结出n 个苹果。苹果成熟的时候，陶陶就会 跑去摘苹果。 陶陶的手不能弯(他仅能把手伸直)，当且仅当陶陶达到的高度与苹果的高度相等的时候，陶陶 才能摘到苹果。 好在陶陶有m 个板凳，每个板凳的高度可以在区间[li; ri] 之间上下移动(即可以随时变为该区 间中任何一个值)。当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。 但是搬板凳对陶陶来说是一件费力的事情，所以他只能选择k 个板凳来使用。 现在已知n 个苹果到地面的高度，m 个板凳的高度区间，陶陶能选择的板凳数k，以及陶陶把 手伸直能达到的高度h，请帮陶陶算一下她最多能够摘到的苹果的数目。假设她碰到苹果，苹果就 会掉下来。

第一行四个正整数n; m; h; k，表示苹果的数量、板凳的数量、陶陶把手伸直能达到的高度和陶 陶最多选择的板凳数量。 第一行包含n 个正整数，第i 个正整数ai 表示第i 个苹果到地面的高度，两个相邻的整数之间 用一个空格隔开。 接下来m 行，每行两个非负整数li; ri，表示第i 个板凳的高度区间。

第一行四个正整数n; m; h; k，表示苹果的数量、板凳的数量、陶陶把手伸直能达到的高度和陶 陶最多选择的板凳数量。 第一行包含n 个正整数，第i 个正整数ai 表示第i 个苹果到地面的高度，两个相邻的整数之间 用一个空格隔开。 接下来m 行，每行两个非负整数li; ri，表示第i 个板凳的高度区间。

一个数，表示最多摘到的苹果数。

对于30% 的数据：m