Problem
Vers'in son sorti hakkında bir rapor hazırlaması gerekiyor. Metni zaten kafasında oluşturmuştur, geriye sadece yazmak kalır. Rapor iki bölümden oluşacak: ilki n kelime içerecek, ith, ai<'den oluşacak / code> harfler, ikinci — m sözcükleri, j'incisi bj harflerinden oluşur. Kriya dili herhangi bir noktalama işareti içermez. Vers, raporu kareli bir kağıt rulosuna, w hücre genişliğinde yazmalıdır. Rapor iki bölümden oluştuğu için, ruloyu dikey bir çizgiyle tüm genişliğin iki parçasına bölecek, ardından ilk bölümü sol tarafa ve sağ tarafa yazacaktır — ikinci.
Raporun her iki kısmı da aynı şekilde, her biri rulonun kendi kısmına yazılır. Kelimenin bir harfi tam olarak bir hücreyi kaplar. İlk kelime, rulonun bu bölümünün en soldaki hücresinden başlayarak rulonun ilk satırına yazılır. Sonraki her kelime, mümkünse, bir öncekiyle aynı satıra yazılmalı ve ondan tam olarak bir boş hücre ile ayrılmalıdır.
Aksi takdirde en soldaki hücreden başlayarak bir sonraki satıra yazılır. Rulonun bir kısmının genişliği, bu kısma yazılması gereken bir kelimenin uzunluğundan azsa, raporun bu kısmını rulonun bu kadar geniş bir kısmına yazmak imkansızdır.
Raporun her iki bölümünün de yazılabilmesi için dikey bir çubuk çizilmesi garanti edilir. Vers, bir rapor yazmak için yeterli olan rulonun uzunluğunun minimum olması için dikey bir çizgi çizmek istiyor. Bu minimum uzunluğu bulmasına yardım edin.
Giriş:
- ilk satır üç tamsayı içerir w, n ve m — rulo genişliği, raporun birinci ve ikinci bölümlerindeki kelime sayısı (\(1 <= w <= 10^9\); \(1 <= n, m <= 100 000\));
- sonraki sonraki satır n tamsayılarını verir ai — raporun ilk bölümünün i. kelimesinin uzunluğu \(1 <= a_i <= 10^9\);
- sonraki satır, m tam sayılarını verir bj — raporun ikinci bölümünün jinci kelimesinin uzunluğu \(1 <= b_j <= 10^9\).
Raporun her iki bölümünün de yazılabilmesi için çizgi çizilmesinin mümkün olduğu garanti edilir.
Giriş: tek bir satıra tek bir tamsayı yazdır — bir rapor yazmak için yeterli olan rulonun minimum uzunluğu.
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
15 6 6
2 2 2 3 2 2
3 3 5 2 4 3
|
3 |
Not
Örnek testte, hücrelerin 7. ve 8. sütunları arasına bir çizgi çekilerek ve ardından raporun her iki bölümüne de satır başına iki kelime yazılarak rulo iki parçaya bölünebilir.