حل الشتاء في المزرعة، وهذا يعني الثلج! توجد $N$ بلاطة في الطريق من المنزل إلى الحظيرة، مرقمة $1 \dots N$، وتغطي البلاطة $i$ طبقة ثلج بعمق $f_i$ قدم.

يبدأ Farmer John على البلاطة $1$ ويجب أن يصل إلى البلاطة $N$ لإيقاظ الأبقار. تحمي سقوف المنزل والحظيرة البلاطتين $1$ و$N$ على الترتيب، لذا لا يوجد ثلج عليهما. لكنه يحتاج إلى أحذية ليسير على البلاطات الأخرى!

في حقيبته للطقس السيئ $B$ زوج من الأحذية، مرقمة $1 \dots B$. بعضها أكثر تحملاً وبعضها أكثر مرونة. يتيح الزوج $i$ السير في ثلج عمقه لا يتجاوز $s_i$ قدم، والتقدم بما لا يتجاوز $d_i$ بلاطة في الخطوة الواحدة.

للأسف، لا يمكنه الوصول في أي وقت إلا إلى الزوج العلوي. يمكنه ارتداؤه مع التخلص من الزوج القديم، أو التخلص من الزوج العلوي لإتاحة الزوج التالي.

لا يمكنه تبديل الأحذية إلا وهو واقف على بلاطة. إذا كان عليها ثلج بعمق $f$ قدم، فيجب أن يتحمل كل من الزوج الذي يخلعه والزوج الذي يرتديه ثلجاً بعمق $f$ قدم على الأقل. الأزواج المتوسطة التي يتخلص منها دون ارتدائها لا يلزم أن تحقق هذا الشرط.

ساعده في تقليل الهدر بإيجاد أقل عدد من أزواج الأحذية التي يجب التخلص منها للوصول إلى الحظيرة. يمكنك افتراض أنه لا يرتدي أي أحذية في البداية.

الإدخال

يحتوي السطر الأول على العددين الصحيحين $N$ و$B$ مفصولين بفراغ ($2 \leq N,B \leq 250$).

يحتوي السطر الثاني على $N$ عدداً صحيحاً مفصولة بفراغات. العدد في الموضع $i$ هو $f_i$، عمق الثلج على البلاطة $i$ ($0 \leq f_i \leq 10^9$). مضمون أن $f_1 = f_N = 0$.

تحتوي الأسطر الـ $B$ التالية على عددين صحيحين مفصولين بفراغ. الأول في السطر $i+2$ هو $s_i$، أقصى عمق ثلج يتحمله الزوج $i$. الثاني في السطر $i+2$ هو $d_i$، أقصى طول خطوة للزوج $i$. مضمون أن $0 \leq s_i \leq 10^9$ و$1 \leq d_i \leq N-1$.

توصف الأزواج من الأعلى إلى الأسفل، لذلك الزوج $1$ هو الأعلى في الحقيبة، وهكذا.

الإخراج

اطبع عدداً صحيحاً واحداً يمثل أقل عدد من الأزواج التي يجب التخلص منها. مضمون أنه يمكن الوصول إلى الحظيرة.

أمثلة

الإدخال 1

10 4
0 2 8 3 6 7 5 1 4 0
2 3
4 2
3 4
7 1

الإخراج 1

2

مؤلفا المسألة: Brian Dean وDhruv Rohatgi