eolymp
bolt
Try our new interface for solving problems
Məsələlər

Ekspedisiya

Ekspedisiya

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Mesklenitlər dünyanın sonuna səyahətə çıxmağa hazırlaşdılar. Onların bir-birinə N×M salla bağlanmış gəmiləri var. Hər bir salın öz yükgötürmə qabiliyyəti, hər bir mesklenitin də öz çəkisi var. Hər bir salda mesklenitin sayı birdən çox olmamalıdır. Əgər seçilmiş salın yükgötürmə qabiliyyəti mesklenitin çəkisindən az olarsa, onda bədbəxt mesklenit sala minmə zamanı batacaq.

Ekspedisiya rəhbəri mesklenitləri sallara görə yerləşdirməyi düşünür. Ona səyahətə göndərə biləcək mesklenitlərin maksimal sayını təyin etməkdə kömək edin.

Giriş verilənləri

İlk sətirdə NM (1N, M40) ədədləri verilir. Növbəti N sətirin hər biri uyğun salın yükgötürmə qabiliyyətini ifadə edən M ədəd ehtiva edir. (N+2)-ci sətirdə mesklenitlərin K (1N2000) sayı verilir. (N+3)-cü sətir i-cisi i-ci mesklenitin çəkisini ifadə edən K ədəd ehtiva edir. Mesklenitlərin və salların yükgötürmə çəkiləri 10^9-u aşmayan natural ədədlərdir.

Çıxış verilənləri

Ekspedisiya iştirakçılarının mümkün maksimal sayını ifadə edən yeganə ədədi verməli.

Nümunə

Giriş verilənləri #1
3 2
5 10
7 5
5 5
6
9 5 3 5 12 10
Çıxış verilənləri #1
4