+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- As everybody may know, Reza Shiri is our favorite artist. SBU students love his songs and they share them in their telegram groups all the time. In the Newbies 2018, the hardest problem of the contest was about Reza Shiri’s concert. This year you are going to help us with purchasing Reza Shiri’s songs. Since we love Reza Shiri and his songs, we never download his songs for free. Reza Shiri’s songs must be purchased from the authorized stores. Going to the iTunes store, each song can be purchased in one of the following ways: + Buying the whole album + Buying a single track Well, everybody wants to purchase all of the available songs and albums. Unfortunately, having a limited budget, one may not be able to afford buying all of the songs. There are $N$ songs and $M$ albums available. Each song belongs to exactly one Album. Songs are numbered from $1$ to $N$. Albums are numbered from $1$ to $M$. # ورودی The first line of input contains three space-separated integers $N, M,$ and $P$ – denoting the number of songs, the number of albums, and our budget respectively. The description of songs is given in the following $N$ lines. $$1 \leq N, M, P \leq 1000$$ Each line consists of 2 space-separated integers $a_i$ and $p_i$ – indicating the album containing this song and the price of this song. In the next line of each test, there are $M$ space separated integers $b_1, b_2, \dots, b_m$ – denoting the price of the albums. $$1 \leq b_i, p_i \leq 10^9$$ $$1 \leq a_i \leq M$$ # خروجی Print the maximum number of songs that we can afford to buy. # مثال‌ها ## ورودی نمونه ۱ ``` 5 2 10 1 3 1 4 1 2 2 1 2 2 7 4 ``` ## خروجی نمونه ۱ ``` 5 ``` In the first test case, it is the best to buy the first album and two songs from the second album. ## ورودی نمونه ۲ ``` 5 2 10 1 3 1 4 1 2 2 1 2 2 8 4 ``` ## خروجی نمونه ۲ ``` 4 ``` In the second test case, it is the best to buy the first album and one song from the second album. ## ورودی نمونه ۳ ``` 5 3 7 1 2 1 2 1 2 1 2 2 2 6 1 3 ``` ## خروجی نمونه ۳ ``` 5 ``` In the third test case, it is the best to buy the first and the second album.

حل سؤال در بانک سؤالات