#include <stdio.h>

 #include <stdlib.h>

 #include <string.h>

 #define MAXNUM 105

 typedef struct {

     int exp, deg;

 } info_st;

 info_st infos[MAXNUM];

 int dp[MAXNUM][MAXNUM];

 int n, m, k, s;

 int comp(const void *a, const void *b) {

     info_st *p = (info_st *)a;

     info_st *q = (info_st *)b;

     if (p->deg == q->deg)

         return q->exp - p->exp;

     else

         return p->deg - q->deg;

 }

 int mymax(int a, int b) {

     return a>b ? a:b;

 }

 int main() {

     int i, j, p, exp, deg;

     while (scanf("%d%d%d%d", &n, &m, &k, &s) != EOF) {

         for (i=; i<k; ++i)

             scanf("%d %d", &infos[i].exp, &infos[i].deg);

         memset(dp, , sizeof(dp));

         qsort(infos, k, sizeof(info_st), comp);

         for (i=; i<k; ++i) {

             exp = infos[i].exp;

             deg = infos[i].deg;

             if (i && deg == infos[i-].deg) {

                 continue;

             }

             for (j=; j<=s; ++j) {

                 for (p=deg; p<=m; ++p) {

                     dp[p][j] = mymax(dp[p][j], dp[p-deg][j-]+exp);

                 }

             }

         }

         for (i=; i<=m; ++i) {

             if (dp[i][s] >= n)

                 break;

         }

         if (i <= m)

             printf("%d\n", m-i);

         else

             printf("-1\n");

     }

     return ;

 }